洛谷 P1879 [USACO06NOV]Corn Fields G（状压DP）

题目链接：https://www.luogu.com.cn/problem/P1879

这道题有些神奇。

首先我们把每一行都压缩成一个二进制数，然后我们考虑在某一块土地上是否种草，是否种草则让j从0~maxstate进行枚举。

只有一种情况是不符合题意的：土地为0，而种草为1。那么即(j&f[i]!=j)就为这种情况。

根据1&1=1,0&1=0,1&0=0,0&0=0。
设x&y=z，那么我们可以发现一个规律，只有当x=0,y=1时，y不等于z。
即可以证明(j&f[i]))!=j的正确性。

其他的就按一个基本的状压DP来即可。

dp[][]：第一维为行数，第二维为状态。

AC代码：

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const ll mod=1e9;
ll dp[20][4100];
int f[4100];
int state[4100];
int main(){
    int m,n;
    scanf("%d%d",&m,&n);
    int maxstate=(1<<n);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            int x;
            scanf("%d",&x);
            f[i]=(f[i]<<1)+x;
        }
    }
    for(int i=0;i<maxstate;i++) state[i]=((i&(i<<1))==0&&(i&(i>>1))==0);
    dp[0][0]=1;
    for(int i=1;i<=m;i++){
        for(int j=0;j<maxstate;j++){
            if(state[j]==0||((j&f[i]))!=j) continue;//太神奇了 
            for(int k=0;k<maxstate;k++) if((j&k)==0) dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
        }
    }
    ll ans=0;
    for(int i=0;i<maxstate;i++){
        ans+=dp[m][i];
        ans%=mod;
    }
    printf("%lld
",ans);
    return 0;
}