符号三角形
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 895 Accepted Submission(s): 454
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
#include <iostream> using namespace std; int result[24]={0,0,4,6,0,0,12,40,0,0,171,410,0,0,1896,5160,0,0,32757,59984,0,0,431095,822229}; int main() { int n; cin>>n; while(n!=0) { cout<<n<<" "<<result[n-1]<<endl; cin>>n; } return 0; }/* hdu 2510 DFS 打表 1^1=0; 1^0=1, 0^1=1 , 0^0=0; 把-‘-’当作1，‘+’当作0时； */ #include<iostream> #include<stdio.h> using namespace std; int map[25][25],count,ans[25]; void DFS(int n) { int i,j; if(n>24) return; for(i=0;i<=1;i++) { map[1][n]=i;//暴力搜索第一行就是最高最长的 n行 枚举 count+=i;// 统计-号的个数 for(j=2;j<=n;j++)//j是行号 { map[j][n-j+1]=map[j-1][n-j+1]^map[j-1][n-j+2]; //下面一行与上一行的关系 下一行比上一行少1个 n-j+1：代表第几行的个数 count+=map[j][n-j+1]; } if(n*(n+1)/2==count*2)//如果- 与 + 号个数相同 { ans[n]++; } DFS(n+1); count-=i; for(j=2;j<=n;j++)////回溯，判断另一种符号情况 //像是出栈一样，恢复所有对counter的操作 { map[j][n-j+1]=map[j-1][n-j+1]^map[j-1][n-j+2]; count-=map[j][n-j+1]; } } } int main() { int count=0,n; DFS(1); while(scanf("%d",&n)!=EOF) { printf("%d\n",ans[n]); } return 0; }