Posted on 2012-03-20 11:34
C小加 閱讀(1658)
評論(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;
}