符号三角形
Time Limit: 2000/1000 MS (
Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 860 Accepted Submission(s): 437
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
int ans[] = {0, 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;
while(scanf("%d", &n), n)
printf("%d %d\n", n, ans[n]);
return 0;
}
打表代码：
#include
int arr[26][26], ans[26], count;
void DFS(int n){
if(n > 24) return;
for(int i = 0; i <= 1; ++i){
arr[1][n] = i;
count += arr[1][n];
for(int j = 2; j <= n; ++j){
arr[j][n-j+1] = arr[j-1][n-j+1] ^ arr[j-1][n-j+2];
count += arr[j][n-j+1];
}
if(count * 2 == (1 + n) * n / 2) ++ans[n];
DFS(n + 1);
//backTrack
count -= arr[1][n];
for(int j = 2; j <= n; ++j){
arr[j][n-j+1] = arr[j-1][n-j+1] ^ arr[j-1][n-j+2];
count -= arr[j][n-j+1];
}
}
}
int main(){
int n; DFS(1);
for(int i = 1; i < 25; ++i)
printf("%d, ", ans[i]);
return 0;
}