给出一个n行m列的草地，1表示肥沃，0表示贫瘠，现在要把一些牛放在肥沃的草地上，但是要求所有牛不能相邻，问你有多少种放法。

假设第 q 行总共有 k 种放法。
对于第 i 行的第 j 种放法，其放置奶牛方法的总数为 i – 1行中不与第 j 种放法冲突的总和。这样利用动态规划，就可以得到第ｎ行总共有多少种方法。

利用到了状态压缩的动态规划，就是相当于枚举子集，利用枚举的子集当成状态来进行转移。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;
}

去打赏