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