【AcWing 327. 玉米田】状压dp

题目链接

题意：

农夫约翰的土地由 M×N 个小方格组成，现在他要在土地里种植玉米。

非常遗憾，部分土地是不育的，无法种植。

而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小，请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式
第 1 行包含两个整数 M 和 N。

第 2…M+1 行：每行包含 N 个整数 0 或 1，用来描述整个土地的状况，1 表示该块土地肥沃，0 表示该块土地不育。

输出格式
输出总种植方法对 108 取模后的值。

分析：

枚举每行的可以种植的状态，这个状态就是和题目中给出的状态取个或就行，然后对每种状态判断一下是否合法然后再枚举转移的状态就可以，下面看代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 13,mod = 1e8;
typedef long long LL;
LL f[N][1<<N];
int g[N];
vector<int> hefa;
int main(){
    
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
    
		int x;
		for(int j=1;j<=m;j++){
    
			cin>>x;
			g[i] = g[i]*2 + x;
		}
	}
	for(int i=0;i<(1<<m);i++){
    
		if((i&(i>>1))==0) hefa.push_back(i);
	}
	f[0][0] = 1;
	LL ans = 0;
	for(int i=1;i<=n;i++){
    
		for(auto j : hefa){
    
			if((g[i]|j) == g[i]){
    
				for(auto x : hefa){
    
					if((j&x)==0)
						f[i][j] = (f[i][j]+f[i-1][x])%mod;
				}
			}
			if(i == n) ans = (ans + f[i][j]) % mod;
		}
	}
	cout<<ans<<endl;
	return 0;
}