2990:符号三角形
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
符号三角形的第1行有n个由“+”和”-“组成的符号 ，以后每行符号比上行少1个，2个同号下面是”+“，2个异号下面是”-“ 。计算有多少个不同的符号三角形，使其所含”+“ 和”-“ 的个数相同。
n=7时的1个符号三角形如下:
+ + - + - + +
+ - - - - +
- + + + -
- + + -
- + -
- -
+ - 输入
- 每行1个正整数n<=24,n=0退出.
- 输出
- n和符号三角形的个数.
- 样例输入
-
15
16
19
20
0 - 样例输出
-
15 1896
16 5160
19 32757
20 59984
分析:
这道题其实就是道水题.当然如果数据再强一点.那就会很难了.不过Openjudge里的数据.这道题很水.而且,就是样例.所以这里可以采用暴力枚举位数.之后再加进行判断.如果这个枚举的可以,那就可以.恩.其实就是这样.不过.我在判断的时候加了个如果某个符号总数已经大于总位数的一半那就不行.这个小剪枝其实还是有点用的.具体还有什么其他的没想出来.希望各位dalao写完之后提些建议//.
#include<cstdio>
#include<algorithm>
using namespace std;
int line[25][25],cnt,sum,num[2],ans,n,num_1[2];
int DFS(int x);
int DFS_1(int x)
{
if(x>n)
{
num[1]=num_1[1];num[0]=num_1[0];
if(DFS(2))ans++;
return 0;
}
for(int i=0;i<=1;++i)
{
line[1][x]=i;
num_1[i]++;
DFS_1(x+1);
num_1[i]--;
}
return 0;<
}
int DFS(int x)
{
if(x==n){
line[x][1]=(line[x-1][1]==line[x-1][2] ? 1:0);
num[line[x][1]]++;
if(num[1]==num[0])return 1;
return 0;
}
for(int i=1;i<=n-x+1;++i)
{
line[x][i]=(line[x-1][i]==line[x-1][i+1] ? 1:0);
num[line[x][i]]++;
if(num[line[x][i]]>(sum/2+1))return 0;
}
if(!DFS(x+1))return 0;
return 1;
}
int main()
{
while(1)
{
scanf("%d",&n);
if(!n)break;
sum=0;ans=0;
for(int i=1;i<=n;++i)sum+=i;
num[1]=0;num[0]=0;
DFS_1(1);
printf("%d %d\n",n,ans);
}
return 0;
}