[POJ3254] Corn Fields
2017年9月14日给出一个n行m列的草地,1表示肥沃,0表示贫瘠,现在要把一些牛放在肥沃的草地上,但是要求所有牛不能相邻,问你有多少种放法。
假设第 q 行总共有 k 种放法。
对于第 i 行的第 j 种放法,其放置奶牛方法的总数为 i – 1行中不与第 j 种放法冲突的总和。这样利用动态规划,就可以得到第n行总共有多少种方法。
利用到了状态压缩的动态规划,就是相当于枚举子集,利用枚举的子集当成状态来进行转移。dp[i][j]
为第 i 行第 j 种状态总共有多少种放法,那么就有 dp[i][j] = (dp[i][j] + dp[i - 1][k]) % md
,其中,k 为 i – 1行的放法,j 与 k 需满足地形,且满足两种状态表示出来的牛不相邻。条件的判断方法用二进制的位运算来就好了。
链接:http://poj.org/problem?id=3254
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 15;
const int md = 100000000;
int cur[N];
int dp[N][1 << 13];
int main()
{
int m, n;
scanf("%d %d", &m, &n);
for (int i = 1; i <= m; i++) {
for (int j = 0; j < n; j++) {
int x;
scanf("%d", &x);
if (!x) {
cur[i] |= 1 << j;
}
}
}
for (int i = 1; i <= m; i++) {
for (int j = 0; j < 1 << n; j++) {
if (cur[i] & j || j & j << 1) {
continue;
}
if (i == 1) {
dp[i][j] = 1;
continue;
}
for (int k = 0; k < 1 << n; k++) {
if (k & k << 1 || cur[i - 1] & k || k & j)
continue;
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % md;
}
}
}
int ans = 0;
for (int i = 0; i < 1 << n; i++) {
ans = (ans + dp[m][i]) % md;
}
printf("%d\n", ans);
return 0;
}