时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
如下图是由14个“+”和14个“-”组成的符号三角形, 2个同号下面都是“+”，2个异号下面都是“-”
- + + - + + + - + - - + + - - + - + + - - - - + + - + - 输入描述 Input Description
一个数n，表示符号三角形的第一行有n个符号
输出描述 Output Description
对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同(严禁打表！！！！！）
若不存在方案，输出-1
样例输入 Sample Input
4
样例输出 Sample Output
6
数据范围及提示 Data Size & Hint
对于90%的数据，n<=24;
对于另外10%的数据，请注意特殊情况。分类标签 Tags
思路：写了个搜索，发现只能卡到70分，然后就用这个暴力打了个表，然后就过了。
#include#include #include #include #define MAXN 2500using namespace std;int n,sum,ans;int map[MAXN][MAXN];int judgenum(){ int bns=0,k; for(int i=2;i<=n;i++){ for(int j=1;j<=n-i+1;j++){ if(map[i-1][j]!=map[i-1][j+1]) map[i][j]=0,bns++; else if(map[i-1][j]==map[i-1][j+1]) map[i][j]=1; } } for(int i=1;i<=n;i++) if(map[1][i]==0) bns++; if(bns==sum-bns) return 1; else return 0; }void dfs(int now,int num1,int num2){ if(now==n+1){ if(judgenum()) ans++; return ; } map[1][now]=1;dfs(now+1,num1+1,num2);map[1][now]=-1; map[1][now]=0;dfs(now+1,num1,num2+1);map[1][now]=-1;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) sum+=i; if(sum%2!=0){ cout<<"-1";return 0; } memset(map,-1,sizeof(map)); dfs(1,0,0); cout<
#include#include #include #include #define MAXN 2500using namespace std;int n,sum,ans;int map[MAXN][MAXN];int anss[25]={ 0,-1,-1,4,6,-1,-1,12,40,-1,-1,171,410,-1,-1,1896,5160,-1,-1,32757,59984,-1,-1,431095,822229};int judgenum(){ int bns=0,k; for(int i=2;i<=n;i++){ for(int j=1;j<=n-i+1;j++){ if(map[i-1][j]!=map[i-1][j+1]) map[i][j]=0,bns++; else if(map[i-1][j]==map[i-1][j+1]) map[i][j]=1; } } for(int i=1;i<=n;i++) if(map[1][i]==0) bns++; if(bns==sum-bns) return 1; else return 0; }void dfs(int now){ if(now==n+1){ if(judgenum()) ans++; return ; } map[1][now]=1;dfs(now+1);map[1][now]=-1; map[1][now]=0;dfs(now+1);map[1][now]=-1;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) sum+=i; if(sum%2!=0){ cout<<"-1";return 0; } cout<