http://poj.org/problem?id=3254
参考:http://blog.csdn.net/accry/article/details/6607703
农夫想在m*n的土地上种玉米,但是有的土地很贫瘠,所以不能种,每块土地标为1的表示能种,标为0的表示不能种,并且种玉米的土地不能相邻,
问有多少种合法的种植方案.(全部不种也算一种)
第一道状压,理解了比较久的时间.
就是用二进制的0和1代表土地种还是不种,这样每一行都可以用一个2进制数表示,列数<=12,故最多有2<<12种状态.
代表一个状态,就可以建立状态转移方程.dp[i][j]代表第i行状态为j时总的方案数,dp[i][j]=sigma(dp[i-1][j']);
判断冲突充分利用了位运算的性质,比如某个状态是否有相邻的1存在则状态x&(x>>1) 或者x&(x<<1)即可.因为等于向左或向右移动一位.
判断是否跟上一行的冲突也是一样.
用滚动数组总是写的不对,好像是初始化的问题.
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
//#include <map>
#include <queue>
#include <deque>
//#pragma comment(linker, "/STACK:102400000,102400000")
#define CL(arr, val) memset(arr, val, sizeof(arr)) #define ll long long
#define INF 0x7f7f7f7f
#define lc l,m,rt<<1
#define rc m + 1,r,rt<<1|1
#define pi acos(-1.0) #define L(x) (x) << 1
#define R(x) (x) << 1 | 1
#define MID(l, r) (l + r) >> 1
#define Min(x, y) (x) < (y) ? (x) : (y)
#define Max(x, y) (x) < (y) ? (y) : (x)
#define E(x) (1 << (x))
#define iabs(x) (x) < 0 ? -(x) : (x)
#define OUT(x) printf("%I64d\n", x)
#define lowbit(x) (x)&(-x)
#define Read() freopen("a.txt", "r", stdin)
#define Write() freopen("b.txt", "w", stdout);
#define maxn 110
#define maxv 5010
#define mod 1000000000
using namespace std;
int n,m,top=;
int state[],num[];
int dp[][]; //最多是600个状态,不知道是以什么方式算出来的
int cur[];
inline bool ok(int x) //判断同一行是否有相邻的1
{
if(x&x<<) return ;
return ;
}
void init() //初始化 2^m个状态,把有相邻1的状态的去掉
{
top=;
int total=<<m;
for(int i=;i<total;i++)
if(ok(i)) state[++top]=i;
}
inline bool fit(int x,int k) //判断状态x和读入的第k行是否冲突,注意cur[k]中1代表不能种,
{ //所以只要相与为1则表示不行
if(x&cur[k]) return ;
return ;
}
int main()
{
//Read();
while(~scanf("%d%d",&n,&m))
{
init();
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)
{
cur[i]=;
int num;
for(int j=;j<=m;j++) //这里是为0表示可以种,为1表示是不可以种
{ //注意和上面区分,这里主要是为了判断冲突.
scanf("%d",&num);
if(!num) cur[i]+=(<<(m-j));//把每一行转换成2进制,并用cur存储
}
//printf("%d\n",cur[i]);
}
for(int i=;i<=top;i++) //初始化第一行,
{
if(fit(state[i],)) //不冲突表示可以放
dp[][i]=;
}
for(int i=;i<=n;i++)
{
for(int j=;j<=top;j++)
{
if(!fit(state[j],i)) continue; //判断第i行和读入的图是否冲突
for(int k=;k<=top;k++)
{
if(!fit(state[k],i-)) continue; //判断第i-1行是否冲突
if(state[j]&state[k]) continue;//判断第i行和第i-1行是否冲突
dp[i][j]=(dp[i][j]+dp[i-][k])%mod;
}
}
}
int ans=;
for(int i=;i<=top;i++)
{
ans=(ans+dp[n][i])%mod;
}
printf("%d\n",ans);
}
return ;
}