NOJ 491 幸运三角形

题目链接~~>

                这题开始用深搜写，但是超时，无奈之下只好打表，交上看了一下别人的基本上都打得表，做完之后又学习了一下大牛的深搜。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #define M 30
     
    
   

    

     

    
    

     

      int n,sum,half ;  // sum 记录一共有几种情况 half 代表可以安放的总数的一半
     
    
   

    

     

    
    

     

      int num[M][M],res[M][M] ;// num[][] 记录放的情况，res[][] 存储前 x 个位置（已经安放的位置）
     
    
   

    

     

    
    

     

      void dfs(int p) // 已经放了几个'+'（相当于动态规划的记忆化的数组）。
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(p>n)// 找到一种方案
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sum++ ;
     
    
   

    

     

    
    

     
 return ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(int i=0 ;i<2 ;i++) // 在第 p 个位置放'-'（1）或'-'（0）
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int count=0 ; // count 记录一共有多少个‘+’
     
    
   

    

     

    
    

     

       num[1][p]=i ; //把第一行放上'+'或'-'
     
    
   

    

     

    
    

     

       count+=res[1][p-1]+i ;
     
    
   

    

     

    
    

     
 for(int j=2 ;j<=p ;j++)   // 依次递推计算出能推出来的
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       num[j][p-j+1]=num[j-1][p-j+1]^num[j-1][p-j+2] ;
     
    
   

    

     

    
    

     
 if(num[j][p-j+1])  // 记录'+'的数量
     
    
   

    

     

    
    

     

       count++ ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       res[1][p]=count ; // 记录已经安放的符号安放了几个'+' 
     
    
   

    

     

    
    

     
 if(count<=half&&p*(p+1)/2-count<=half) //已经安放的'+'或'-'的数量都不能超过总数的一半
     
    
   

    

     

    
    

     

       dfs(p+1) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 while(scanf("%d",&n)!=EOF)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sum=half=0 ;
     
    
   

    

     

    
    

     
 if((n*(n+1)/2)%2==0)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       half=n*(n+1)/4 ;
     
    
   

    

     

    
    

     

       dfs(1) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("%d\n",sum) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/16115113