C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

sgu 223 Little Kings(状态压缩DP)

Posted on 2012-03-20 11:34 C小加 阅读(1563) 评论(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;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理