状压dp POJ 3254 Corn Fields

链接：http://poj.org/problem?id=3254

题意：m*n的矩阵，每个格子中都有个0或者1，0表示不能放牧，1表示可以放牧，要求不能出现相邻的牧场都放牧了。求方案总数

注意到这个题的m和n都特别小，都不超过12

那么：想到状态压缩

枚举每一行的所有放牧的方案，用1表示放牧，用0表示不放牧，每一个数的二进制展开均为0和1的形式

那么：所有的状态总数也是很小的：2^12 = 4096种

题目要求：相邻的不能放牧：上下左右称为相邻，也就是说，当前行的枚举判断的条件，只与当前行的状态与上一行的状态有关系。定义dp[i][j]：前i行，且第i行状态为j时的方案数

考虑状态转移：我们需要枚举第i-1行的状态k，首先k是个合法的没有左右放牧相邻的状态，然后再使得j和k在放牧时候不相邻也就是处理了上下关系~

则有：dp[i][j] = sum(dp[i-1][k])

代码如下：

#include <cstdio>
#include <cstring>
using namespace std;

#define mod 100000000
int M,N,tot;
int state[600],num[110];
int dp[20][600];
int cur[20];

bool ok(int x){
	if (x & (x<<1)) return false;
	return true;
}

void init(){
	tot=0;
	int maxnum=1<<N;
	for(int i=0;i<maxnum;i++)
		if (ok(i)) state[++tot]=i;
}

bool fit(int x,int k){
	if (x & cur[k]) return false;
	return true;
}

int main(){
	//freopen("input.txt","r",stdin);
	while(scanf("%d%d",&M,&N)!=EOF){
		init();
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=M;i++){
			cur[i]=0;
			int num;
			for(int j=1;j<=N;j++){
				scanf("%d",&num);
				if (!num) cur[i] += (1<<(N-j));
			}
		}
		for(int i=1;i<=tot;i++)
			if (fit(state[i],1))
				dp[1][i]=1;
		for(int i=2;i<=M;i++)
			for(int k=1;k<=tot;k++)
				if (fit(state[k],i))
					for(int j=1;j<=tot;j++)
						if (fit(state[j],i-1))
							if (!(state[k] & state[j]))
								dp[i][k] = (dp[i][k]+dp[i-1][j])%mod;
		int ans=0;
		for(int i=1;i<=tot;i++)
			ans = (ans+dp[M][i])%mod;
		printf("%d\n",ans);
	}
	return 0;
}