符号三角形
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 929 Accepted Submission(s): 474
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打表，发现规律。
+ + - + - + +
+ - - - - +
- + + + -
- + + -
- + -
- -
+
DFS时每次增加一行仅需改变头字符的类型，且满足
map[step][j]=map[step][j-1]^map[step-1][j-1];
*/
题解：DFS打表，发现规律。
+ + - + - + +
+ - - - - +
- + + + -
- + + -
- + -
- -
+
DFS时每次增加一行仅需改变头字符的类型，且满足
map[step][j]=map[step][j-1]^map[step-1][j-1];
*/
打表代码：
#include<cstdio>
#include<cstring>
int map[30][30],res[30];
void dfs(int step,int s)
{
int ans;
for(int i=0; i<2; i++)
{
map[step][0]=i;
ans=i;
for(int j=1; j<step; j++)
{
map[step][j]=map[step][j-1]^map[step-1][j-1];
ans+=map[step][j];
}
if((1+step)*step/2==(ans+s)*2) res[step]++;
if(step==24) continue;
dfs(step+1,s+ans);
}
}
int main()
{
memset(res,0,sizeof(res));
memset(map,0,sizeof(map));
dfs(1,0);
for(int i=1; i<=24; i++)
{
printf("%d, ",res[i]);
}
while(1);
}
#include<cstdio>
int main(){
int n,table[]={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};
while(scanf("%d",&n)&&n){
printf("%d %d\n",n,table[n]);
}
return 0;
}