2010年1月14日星期四.pku3254 状态压缩动态规划
pku3254:状态压缩动态规划
题目给出了一个m*n(m,n<=12)的矩阵，1代表此点可以放玉米，0代表不可放
求 最后可能的放置方案有多少种?
题目中给出了一个例子
2 3
1 1 1
0 1 0
对于这个例子，放置的方法一共有9种
这个题相对于1185 炮兵阵地来说要好做一些，只要记录上一行的状态，就可以了，不用记录
上上行的状态。
方法也是先枚举出一行中的所有可行状态。
然后根据这些可行状态按行递推，中间还要记得判断状态是否和地形不冲突。
注意运算符的优先级，按照以下形式写成的宏定义会比较安全
#define bin(i) (1 << (i))
#define L(i) ((i) << 1)
#define R(i) ((i) >> 1)
const int N = 13;
int f[N][bin(N)];
int full,s[bin(N)],top,m,n,terrain[N];
bool contradict(int x)
{
return x & L(x);
}
bool sameRow(int a,int b)
{
return (a&b);
}
void preproc()
{
int i;
for(i = 0;i <= full;i++) {
if(!contradict(i)) {
s[top++] = i;
}
}
}
int main()
{
int i,j,k;
scanf("%d%d",&n,&m);
memset(f,0,sizeof(f));
full = bin(m) - 1;
preproc();
for (i = 1;i <= n;i++) {
int tmp = 0;
for (j = 1;j <= m;j++) {
scanf("%d",&k);
tmp = L(tmp) + (1 - k);
}
terrain[i] = tmp;
}
f[0][0] = 1;
for(i = 1;i <= n;i++) {
for(j = 0;j < top;j++) {
if(s[j] & terrain[i]) continue;
for(k = 0;k < top;k++) {
if(!sameRow(s[j],s[k])) {
f[i][j] =(f[i][j] + f[i-1][k])%100000000;
}
}
}
}
//http://www.cppblog.com/schindlerlee
int res = 0;
for(i = 0;i < top;i++) {
res =(res + f[n][i])%100000000;
}
cout << res << endl;
return 0;
}