题解 P1879 【[USACO06NOV]Corn Fields G】

数据范围肉眼可见状压DP

考虑选择套路的状态设计方式，令$dp_{i,j}$为截至第$i$行，第$i$行的状态为$j$情况下的方案数。
转移的时候，枚举上一级的状态来更新即可，边界条件为$dp_{0,0}=1$。
更新的方法上，可以枚举j的补集的子集来进行更新。
时间复杂度$O(n\times 3^n)$

#include<iostream>
using namespace std;
int a[15][15],f[15];
int dp[15][5005];
int main(){
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			f[i]=(f[i]<<1)+a[i][j];
		}
	}
	dp[0][0]=1;
	for(int i=1;i<=m;i++){
		for(int j=0;j<(1<<n);j++){
			if(((j&(j<<1))==0)&&((j&(j>>1))==0)&&((j&f[i])==j)){
				int x=((1<<n)-1)^j;
				for(int k=x;k;k=((k-1)&x)){
					dp[i][j]+=dp[i-1][k];
					dp[i][j]%=(int)(1e9);
				}
				dp[i][j]+=dp[i-1][0];
				dp[i][j]%=(int)(1e9);
			}
		}
	}
	int ans=0;
	for(int j=0;j<(1<<n);j++){
		ans+=dp[m][j];
		ans%=(int)(1e9); 
	}
	cout<<ans;
	return 0;
}