符号三角形（hdu 2510 搜索+打表）

符号三角形

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1246    Accepted Submission(s):
664

Problem Description

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

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

 

Input

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

 

Output

n和符号三角形的个数.

 

Sample Input

15

16

19

20

 

Sample Output

15 1896

16 5160

19 32757

20 59984

 

打表代码：

 #include <iostream>
 #include <cstring>
 #include <cstdio>
 using namespace std;
 int a[];
 char res[][];
 int    sum;
 bool count(int n)
 {
     int p1=,p2=;
     int i,j;
     for(i=;i<=n;i++)
     {
         if(res[][i]=='+')    p1++;
         else    p2++;
     }
     for(int i=;i<n;i++)
         for(j=;j<=n-i;j++)
         {
             res[i][j]=(res[i-][j]==res[i-][j+]?'+':'-');
             if(res[i][j]=='+')    p1++;
             else    p2++;
         }
     if(p1==p2)
         return ;
     return ;
 }
 void dfs(int n,int s)
 {
     int i,j;
     if(s>n)
     {
         if(count(n))
             sum++;
         return;
     }
     res[][s]='+';
     dfs(n,s+);
     res[][s]='-';
     dfs(n,s+);
     return;
 }
 int main()
 {
     int n;
     int i,j;
     a[]=a[]=;
     for(i=;i<=;i++)
     {
         sum=;
         dfs(i,);
         a[i]=sum;
         cout<<a[i]<<endl;
     }
 }