HDU2510 符号三角形 DFS直接打表

Problem Description

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

Input

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

Output

n和符号三角形的个数.

Sample Input

Sample Output

15 1896

16 5160

19 32757

20 59984

这道题本来是尝试找规律的，找了4个，发现应该是没有规律的，网上看了一下，说是可以打表，哈哈，打表的题目我还没有做过，就做了，挺好玩的。

打表，就是DFS (或其他方式) 找出所有情况，看哪些情况符合题意的要求，就记录下来，用一个数组存储，然后在程序中直接就把数组写上去了，挺爽的。

我的打表程序：

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=28;
 4 int a[maxn][maxn];
 5 int n;
 6 int ans,add,sub;
 7 void DFS(int cnt)
 8 {
 9     if(cnt==n+1)
10     {
11         for(int i=n-1;i>0;i--)
12         {
13             for(int j=1;j<=i;j++)
14             {
15                 a[i][j]=a[i+1][j]^a[i+1][j+1];
16             }
17         }
18         sub=add=0;
19         for(int i=1;i<=n;i++)
20         {
21             for(int j=1;j<=i;j++)
22                 if(a[i][j]==1)
23                     sub++;
24                 else
25                     add++;
26         }
27         if(add==sub)
28             ans++;
29         return ;
30     }
31     for(int i=0;i<=1;i++)
32     {
33         a[n][cnt]=i;
34         DFS(cnt+1);
35     }
36 }
37 int main()
38 {
39     while(scanf("%d",&n))
40     {
41         memset(a,-1,sizeof(a));
42         ans=0;
43         DFS(1);
44         printf("%d
",ans);
45     }
46     return 0;
47 }

我的打表代码

 1 #include<cstdio>
 2 int a[25]={0,0,0,4,6,0,0,12,40,0,0,171,410,0,0,1896,5160,0,0,32757,59984,
 3             0,0,431095,822229};
 4 int main()
 5 {
 6     int n;
 7     while(scanf("%d",&n))
 8     {
 9         if(n==0)
10             break;
11         printf("%d %d
",n,a[n]);
12     }
13     return 0;
14 }

我的提交代码