bzoj1725&poj3254: [Usaco2006 Nov]Corn Fields牧场的安排 状压dp
Description
Farmer John新买了一块长方形的牧场,这块牧场被划分成M列N行(1<=M<=12; 1<=N<=12),每一格都是一块正方形的土地。FJ打算在牧场上的某几格土地里种上美味的草,供他的奶牛们享用。遗憾的是,有些土地相当的贫瘠,不能用来放牧。并且,奶牛们喜欢独占一块草地的感觉,于是FJ不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边。当然,FJ还没有决定在哪些土地上种草。 作为一个好奇的农场主,FJ想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择。当然,把新的牧场荒废,不在任何土地上种草,也算一种方案。请你帮FJ算一下这个总方案数。
Input
-
第1行: 两个正整数M和N,用空格隔开
-
第2..M+1行: 每行包含N个用空格隔开的整数,描述了每块土地的状态。输入的第i+1行描述了第i行的土地。所有整数均为0或1,是1的话,表示这块土地足够肥沃,0则表示这块地上不适合种草
Output
- 第1行: 输出一个整数,即牧场分配总方案数除以100,000,000的余数
题解
首先根据(n),(m)范围可以看出状压dp。于是我们预处理一行的所有情况(0 ~ ((1 << n) - 1)),即用二进制表示草的情况,1代表有草,0代表无草。
原数与自己左移一位和自己右移一位的&运算结果为0符合题意。
然后我们将题目给的地图信息一行一行按二进制存下来,然后(dp)扫。若(j & a[i] ) == j说明没有在不能种草的地方种草。然后根据上一行的情况更新答案即可。
(f[i][j])中(i)表示第几行,(j)表示草地铺设情况(二进制)
[f[i][j]=f[i][j]+f[i-1][k]
]
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1e9;
const int maxn=1<<12+1;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int m,n;
int mp[13][13];
int a[13];
int is[maxn];
int f[13][maxn];
int ans;
int main(){
m=read();n=read();
for(int i=0;i<(1<<n);i++)
if(((i&(i<<1))==0)&&((i&(i>>1))==0))
is[i]=1;
for(int i=1;i<=m;i++) for(int j=1;j<=n;j++)
mp[i][j]=read(),a[i]=(a[i]<<1)+mp[i][j];
for(int i=0;i<(1<<n);i++)if(is[i]&&(i&a[1])==i)f[1][i]=1;
for(int i=2;i<=m;i++) for(int j=0;j<(1<<n);j++)
if(is[j]&&(j&a[i])==j) for(int k=0;k<(1<<n);k++)
if((j&k)==0) f[i][j]=(f[i][j]+f[i-1][k])%mod;
for(int i=0;i<(1<<n);i++)
ans=(ans+f[m][i])%mod;
printf("%d
",ans);
return 0;
}