状态压缩dp入门（poj3254 Corn Fields）

快来打我* 2022-08-27 02:24 156阅读 0赞

题目链接：[http://poj.org/problem?id=3254][http_poj.org_problem_id_3254]

题意：给出一个n行m列的草地，1表示肥沃，0表示贫瘠，现在要把一些牛放在肥沃的草地上，但是要求所有牛不能相邻，问你有多少种放法。

分析：假如我们知道第 i-1 行的所有的可以放的情况，那么对于第 i 行的可以放的一种情况，我们只要判断它和 i - 1 行的所有情况的能不能满足题目的所有牛不相邻，如果有种中满足，那么对于 i 行的这一中情况有 x 中放法。

前面分析可知满足子状态，我们我们确定可以用dp来解决。

但是我们又发现，状态是一种放法，不是我们平常dp的简单的状态，所以要用状态压缩！

但是什么是状态压缩呢?

比如前面的情况，一种放法是最多由12个 0 或者 1 组成的，那么我们很容易想到用二进制，用二进制的一个数来表示一种放法。

定义状态dp【i】【j】，第 i 行状态为 j 的时候放牛的种数。j 的话我们转化成二进制，从低位到高位依次 1 表示放牛0表示没有放牛，就可以表示一行所有的情况。

那么转移方程 dp【i】【j】=sum（dp【i-1】【k】）

状态压缩dp关键是处理好位运算。

这个题目用到了 & 这个运算符。

用 x & （x<<1）来判断一个数相邻两位是不是同时为1，假如同时为 1 则返回一个值，否则返回 0 ，这样就能优化掉一些状态

用 x & y 的布尔值来判断相同为是不是同时为1。

代码：

#include <cstdio>
    #include <cstring>
    const int N = 13;
    const int M = 1<<N;
    const int mod = 100000000;
    int st[M],map[M];  ///分别存每一行的状态和给出地的状态
    int dp[N][M];  //表示在第i行状态为j时候可以放牛的种数
    bool judge1(int x)  //判断二进制有没有相邻的1
    {
        return (x&(x<<1));
    }
    bool judge2(int i,int x)
    {
        return (map[i]&st[x]);
    }
    int main()
    {
        int n,m,x;
        while(~scanf("%d%d",&n,&m))
        {
            memset(st,0,sizeof(st));
            memset(map,0,sizeof(map));
            memset(dp,0,sizeof(dp));
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++){
                    scanf("%d",&x);
                    if(x==0)
                        map[i]+=(1<<(j-1));
                }
    
            }
            int k=0;
            for(int i=0;i<(1<<m);i++){
                if(!judge1(i))
                    st[k++]=i;
            }
            for(int i=0;i<k;i++)
            {
                if(!judge2(1,i))
                    dp[1][i]=1;
            }
            for(int i=2;i<=n;i++)
            {
                for(int j=0;j<k;j++)
                {
                    if(judge2(i,j))  //判断第i行 假如按状态j放牛的话行不行。
                        continue;
                    for(int f=0;f<k;f++)
                    {
                        if(judge2(i-1,f))   //剪枝 判断上一行与其状态是否满足
                            continue;
                        if(!(st[j]&st[f]))
                            dp[i][j]+=dp[i-1][f];
                    }
                }
            }
            int ans=0;
            for(int i=0;i<k;i++){
                ans+=dp[n][i];
                ans%=mod;
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[http_poj.org_problem_id_3254]: http://poj.org/problem?id=3254