幸运三角形http://acm.nyist.net/JudgeOnline/problem.php?pid=491

本文主要是介绍幸运三角形http://acm.nyist.net/JudgeOnline/problem.php?pid=491，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

经典的dfs题，子集的构造方法为难点。。

AC代码：

#include<iostream>
#include<cstdio>
#include<string.h>
#define N 25
using namespace std;
bool num[N][N];
int res[N][N];
int n,sum,half;
void dfs(int cur)
{
if(cur==n+1){sum++;return;}
for(int i=0;i<2;++i)//子集生成：位向量法
{
int count=0;
num[1][cur]=i;//这里0表示'-'，1表示'+'.
count=res[1][cur-1]+i;//当前+号的个数为新增加的一个和原来的总数和
for(int j=2;j<=cur;++j)
{
num[j][cur-j+1]=num[j-1][cur-j+1]^num[j-1][cur-j+2];
if(num[j][cur-j+1]) count++;
}
res[1][cur]=count;
if(count<=half&&(cur+1)*cur/2-count<=half) dfs(cur+1);//剪枝
//当搜索到深度为cur时，生成子集的总个数。
}
}
int main()
{
while(~scanf("%d",&n))
{
sum=0;
memset(res,0,sizeof(res));
int m=(n+1)*n/2;
if(m&1){printf("0\n");continue;}//当图形的总数为奇数时，剪枝
half=m/2;
dfs(1);
printf("%d\n",sum);
}return 0;
}

 

 

这篇关于幸运三角形http://acm.nyist.net/JudgeOnline/problem.php?pid=491的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---