符号三角形

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1800    Accepted Submission(s): 930 Problem Description 符号三角形的 第1行有n个由“+”和”-“组成的符号 ，以后每行符号比上行少1个，2个同号下面是”+“，2个异 号下面是”-“ 。计算有多少个不同的符号三角形，使其所含”+“ 和”-“ 的个数相同 。 n=7时的1个符号三角形如下: + + - + - + +  + - - - - +  - + + + -  - + + -  - + -  - -  +   Input 每行1个正整数n <=24,n=0退出.   Output n和符号三角形的个数.    Sample Input 15 16 19 20 0   Sample Output 15 1896 16 5160 19 32757 20 59984

分析：dfs代码超时，数据较小，可以打表过，之后再贴优化代码

代码如下：

#include <stdio.h> int N; int count=0; int a[1005][1005]; int judge() { int i,j; long long n=0,m=0; for(j=0;j<N;j++) {//统计第一行的正负个数 if(a[0][j]) n++; else m++; } for(i=1;i<N;i++) { for(j=0;j<N-i;j++) {//统计其他行的正负个数 a[i][j]=!(a[i-1][j]^a[i-1][j+1]); if(a[i][j]) n++; else m++; } } if(n==m) return 1; else return 0; } void dfs(int t) {//t代表层数，a代表加号个数，b代表减号个数 ,index代表上一层是+还是- if(t==N) { if(judge()) count++; return ; } //负号 a[0][t]=0; dfs(t+1); //正号 a[0][t]=1; dfs(t+1); } int main() { while(scanf("%d",&N),N) { count=0; dfs(0); printf("%d\n",count); } return 0; }