2990:符号三角形

总时间限制: 1000ms
内存限制: 65536kB

描述

符号三角形的第1行有n个由“+”和”-“组成的符号 ，以后每行符号比上行少1个，2个同号下面是”+“，2个异号下面是”-“ 。计算有多少个不同的符号三角形，使其所含”+“ 和”-“ 的个数相同。

n=7时的1个符号三角形如下:

+ + - + - + +
+ - - - - +
- + + + - - + + - - + - - - +

输入

每行1个正整数n<=24,n=0退出.

输出

n和符号三角形的个数.

样例输入

15
16
19
20
0

样例输出

15 1896
16 5160
19 32757
20 59984

提示

这是一道典型的深搜（回溯）题，在面对此题时，我们可以倒着来推，即，最后一个变第一个，但记住坐标不可变。如下图：

如果是这样的话，那就应该很简单了，当然，也可以用动规来做，在这里，我们重点讲述深搜，在题中，我们的M当然就为30度角的那个点，要永远记住，它的坐标一定不变（即m,1），即使转换了图像，也不会变。在完成此题时，我以数学思想来思考的，最明显的就是：多种情况考虑。
代码如下，里含注释，如果有同学还有疑问的，可在评论里留言。

代码状态： Accepted

#include<iostream> 
#include<cstring> 
#include<cstdlib> 
#include<cstdio> 
#include<cmath> 
#include<algorithm> 
using namespace std;  const int maxn=25; 
int n; 
long long  anss; 
int map[maxn][maxn]; 
long long  ans[maxn]; void dfs(int m,int z,int f)//把数字三角形倒过来看，一共就两种情况
{ //m当做行，z当做加号数量，f当做减号数量if(z>(n*(n+1)/4)||f>(n*(n+1)/4)) //如果符号数量为总数的一半return; //即+/-号分别为符号的一半，即总数的四分之一
if(m==n+1) { //如果行数达到要求，退出if(z==f) { anss++; //当z==f的时候，加一个} return; } if(m==1) { map[1][1]=1; dfs(m+1,z+1,f); map[1][1]=0; dfs(m+1,z,f+1); } else { //情况一int num_neg=0,num_pos=0; //首位是0 //1是+，0是- map[m][1]=0; //把第一个当做减号时num_neg++; //记录-的+1for(int i=2;i<=m;i++) { if(map[m-1][i-1]==1) //如果m的正下方为+号，{ map[m][i]=map[m][i-1]; //如果m的下一行（正下方）的为+，那么他的上一行一定为两个相等的字符if(map[m][i]) //如果map为+，加号计时器+1num_pos++; else //否则，减号计时器+1num_neg++; } else //否则，m的下一行为减号{ if(map[m][i-1]==1) { map[m][i]=0; //两数不相同，因为m的下一行为减号num_neg++; } else //相同原理{ map[m][i]=1; num_pos++; } } } dfs(m+1,z+num_pos,f+num_neg); //行加一，加号计时器加上，减号计时器加上//情况二num_pos=0; num_neg=0; map[m][1]=1; num_pos++; for(int i=2;i<=m;i++) { if(map[m-1][i-1]) //与上述相同{ map[m][i]=map[m][i-1]; if(map[m][i]) num_pos++; else num_neg++; } else { if(map[m][i-1]) { map[m][i]=0; num_neg++; } else { map[m][i]=1; num_pos++; } } } dfs(m+1,z+num_pos,f+num_neg); //相同的递归} 
}int main()  
{  while(scanf("%d",&n)!=0&&n!=0)  {  anss=0;memset(map,0,sizeof(map));  dfs(1,0,0); //把m当做行数，0为+/-号数量printf("%d %lld\n",n,anss);  }  return 0;  
}