【每日DP】day2、P1879 [USACO06NOV]Corn Fields G玉米地（状压DP模板题）难度⭐⭐⭐★

昨天的每日DP我还在写01背包，今天就到状压DP了，真刺激。

P1879 [USACO06NOV]Corn Fields G
题目链接

输入

2 3
1 1 1
0 1 0

输出

一道简单的状压DP入门题。
先看大佬讲解样例这是链接我截下来放到下面了

本题我的代码的思路

1、先预处理第i行的草地状态 $i n i t [i]$ ，压缩为一个整数。

2、再预处理第i行不相邻的状态 $l e g a l [i]$ ，每行共有 $(1 < < m) - 1$ 种状态，但是很多是存在相邻的情况，所以提前处理不合法的状态可以在状态转移中降低很多时间复杂度。

那么怎么判断某一状态是否相邻呢？只需要 $(i & (i < < 1) = = 0) & & (i & (i > > 1) = = 0)$ 就可以判断,如果存在相邻情况则将 $l e g a l [i]$ 置为 $f a l s e$ ，不存在相邻则为 $t r u e$ 。

3、怎么处理只能放到肥沃的草地呢？对于第i行的地形 $i n i t [i]$ 和某一状态j，如果枚举到的 $i n i t [i] & j = = j$ 即说明了两个状态完全相同，没有放到贫瘠草地的情况。

4、对于第i行不和i-1行有连通草地，枚举上一行方案k，该行方案 $j & k = = 0$ 即可满足条件。

5、这一行的某种方案的方案数为上一行的所有可行的的方案数相加,最后把最后一行的所有方案的方案数相加。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2000+7;
const ll mod=100000000;
ll dp[13][1<<12];//该dp的状态 dp[i][j]为在前i行,此行是方案j时的方案总数 
bitset<1<<12>legal;
ll init[13];
ll n,m,tmp,maxn,sum;
int main()
{
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%lld",&tmp),init[i]=(init[i]<<1)+tmp;//用一串二进制数来表示这一行的情况，所以每输入一个数就左移加上新的数（0/1），将每行有无草坪的初始状态压缩成一个整数 
    maxn=(1<<m)-1;//最大状态,即全部草坪都放牛时的状态 
    for(int i=0;i<maxn;++i)//预处理所有方案有多少是合法的（左右草地不相邻），下面直接用legal来判断一下就好了
        if(!(i&(i<<1))&&!(i&(i>>1)))
            legal[i]=1;//如果枚举到了当前方案，中任意相邻两格之间都没有相邻的草，那么判断此方案合法赋值为1
    dp[0][0]=1;//初始化为1
    for(int i=1;i<=n;++i)//循环每一行
        for(int j=0;j<=maxn;++j)//枚举该行的方案
            if(legal[j]&&((j&init[i])==j))//当前方案合法且与最开始输入的土地情况吻合则该方案合法
                for(int k=0;k<=maxn;++k)//枚举上一行的方案，因为这一行更新需要上一行来传递（DP嘛），所以必须枚举一次上一行，并判断一下上下两行是否不相邻即可，然后更新这一行的答案
                    if(!(k&j))//如果该种方案与上一行方案k不存在公共边,则可以在该方案累加上一行方案k的方案总数，此时不需要考虑上一行方案的合法性,因为上一种方案不合法则本身方案数就为0 
                        dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
    for(int i=0;i<=maxn;++i)
        sum=(sum+dp[n][i])%mod;
    printf("%lld\n",sum);
    return 0;
}

有任何疑问欢迎评论哦~~虽然我真的很菜~~