Posted on 2012-03-20 11:34
C小加 阅读(1602)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
第一个状态压缩啊，调试了一个上午，终于过了，国王的个数原来是从0开始循环的。
周伟大神的论文《状态压缩》很给力，如果不是这篇论文，我都不知道该如何入门了。哎，没人教的杯具。
本题题解《状态压缩》讲的很清楚，我就不多废话了。需要注意的是范围会超int，还有对状态的范围要把握好，搞不好你也要杯具去各种调试了。
自己写的DFS很挫，借用了不知道哪位大牛的DFS。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXM=520;
int n,k;
int s[MAXM];//状态数
int c[MAXM];//1的个数
long long f[13][MAXM][103];
int ck;
void dfs(int x,int val,int cnt)//DFS寻找每行的状态数
{
if(x==n)
{
s[++ck]=val;
c[ck]=cnt;
return;
}
dfs(x+1,val<<1,cnt);
if(!(val&1))
dfs(x+1,val<<1|1,cnt+1);
}
bool cont(int s1,int s2)//判断与题意是否矛盾
{
if(s1&s2) return false;//和正上方判断
if(s1&(s2<<1))return false;//和右上方判断
if(s1&(s2>>1))return false;//和左上方判断
return true;
}
void dp()
{
//初始化状态
memset(f,0,sizeof(f));
f[0][1][0]=1;
//dp
for(int i=1;i<=n;i++)
{
for(int j=1;j<=ck;j++)
{
for(int g=1;g<=ck;g++)
{
for(int p=0;p<=k;p++)
{
if((p-c[j]>=0)&&cont(s[j],s[g]))
f[i][j][p]+=f[i-1][g][p-c[j]];
}
}
}
}
}
int main()
{
while(scanf("%d %d",&n,&k)!=EOF)
{
ck=0;
dfs(0,0,0);
dp();
long long ans=0;
for(int i=1;i<=ck;++i)
{
ans+=f[n][i][k];
}
printf("%I64d\n",ans);
}
return 0;
}