题解 P1879 【[USACO06NOV]玉米田Corn Fields】

· · 题解

前排警告

这是写给刚学的我看的，大佬请自动忽略

人生第一道状压dp 互不侵犯是学术交流过的

本蒟蒻今天在机房听到状压dp，感觉很高大上……其实就是位运算高大上一点

解释一下位运算：

& 给个例子

0110101+1010011=0010001$，返回值为$17 n<<k$ 将$n$左移$k$位，相当于给$n$乘上$2^k #### 解释一下状压$dp$： 它的基本思想就是用二进制来优美地暴力枚举出现的方案， 若二进制下第$i$位有赋值$1$，则一行的第$i$列有放牛 那么$f[i][j]$表示在前$i$行中（包括$i$）在$j$个状态下的最大方案数 易得$f[i][j]=(f[i][j]+f[i-1][k])\ mod\ p$（$p=10^9$，$j$是第$i$行的状态，$k$是第$i-1$行的状态） 所以我们还要再预处理一下，$g[i]$表示第$i$个状态是否存在，判断条件是 $g[i]=$ $!(i$&$(i>>1))!(i$&$(i<<1))

目标状态：f[n][i]全部相加

Code \ Below: 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int p=100000000;
ll f[13][1<<12],n,m;
ll g[1<<12],h[1<<12],a[13][13];
ll F[13];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            F[i]=(F[i]<<1)+a[i][j];
    for(int i=0;i<(1<<m);i++){
        if(!(i&(i>>1))&&!(i&(i<<1))){
            g[i]=1;
            if((i&F[1])==i) f[1][i]=1;
        }
    }
    for(int x=2;x<=n;x++)
        for(int j=0;j<(1<<m);j++)
            if(((j&F[x-1])==j)&&g[j])
                for(int k=0;k<(1<<m);k++)
                    if(((k&F[x])==k)&&!(j&k)&&g[k]){
                        f[x][k]=(f[x][k]+f[x-1][j])%p;
                    }
    int ans=0;
    for(int i=0;i<(1<<m);i++)
        ans=(ans+f[n][i])%p;
    printf("%d\n",ans);
    return 0;
}