poj 3254 Corn Fields

题意：给一个n*m的地图，地图只有1和0组成，0代表不可以放牧，1代表可以放牧；不能有相邻的牛，问有多少种放牧方法。

经典状态压缩         用数组map作为地图用2进制来表示0代表不可以放牧，1代表可以放牧；通过x&x<<1来判断当前状态是否满足题意；

             通过x&y来判断在上一行满足题意的情况在当前行能否满足题意。个人认为状态压缩DP 刚开始蛮不好学的，但是愈战愈勇才是一个ACMer该有的品质！！！

AC代码如下

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int map[15],n,m,tot,cnt;
int dp[15][600];
int vis[600];
int fun1(int x)
{
	if(x&x<<1) return 0;
	return 1;
}
void bulid()
{
	int M=1<<m;
	tot=0;
	for(int i=0;i<M;i++)
	{
		if(fun1(i)) vis[++tot]=i;
	}
}
int fun(int x,int y)
{
	if(x&y)return 0;
	return 1;
}
int main()
{
	int i,j,k,t;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		bulid();
		memset(dp,0,sizeof(dp));
		memset(map,0,sizeof(map));
		for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			scanf("%d",&t);
			if(t==0)
			{
				map[i]=map[i]+(1<<m-j);
			}
		}
		for(i=1;i<=tot;i++)
		{
			if(fun(vis[i],map[1]))
			dp[1][i]=1;
		}
		for(i=2;i<=n;i++)
		{
			for(j=1;j<=tot;j++)
			{
				if(fun(vis[j],map[i]))
				for(k=1;k<=tot;k++)
				{
					if(fun(vis[k],map[i-1]))
					{
						if(fun(vis[k],vis[j]))
						dp[i][j]=(dp[i][j]+dp[i-1][k])%100000000;
					}
				}
			}
		}
		cnt=0;
		//printf("%d\n",tot);
		for(i=1;i<=tot;i++)
		{
			cnt+=dp[n][i];
			cnt%=100000000;
		}
		printf("%d\n",cnt);
	}
}

poj 3254 Corn Fields

原文：http://blog.csdn.net/l133236116/article/details/42918839