[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;
}
去打赏

您的支持将鼓励我们继续创作!

[微信] 扫描二维码打赏

[支付宝] 扫描二维码打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注