玉米田
农夫约翰的土地由 $M \times N$ 个小方格组成，现在他要在土地里种植玉米。
非常遗憾，部分土地是不育的，无法种植。
而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。
现在给定土地的大小，请你求出共有多少种种植方法。
土地上什么都不种也算一种方法。
输入格式
第 $1$ 行包含两个整数 $M$ 和 $N$。
第 $2 \dots M+1$ 行：每行包含 $N$ 个整数 $0$ 或 $1$，用来描述整个土地的状况，$1$ 表示该块土地肥沃，$0$ 表示该块土地不育。
输出格式
输出总种植方法对 ${10}^{8}$ 取模后的值。
数据范围
$1 \leq N,M \leq 12$
输入样例：
2 3 1 1 1 0 1 0
输出样例：
9
解题思路
状态压缩dp。当摆放了绿色的格子后，绿色格子上下左右四个位置（红色格子）都不可以再摆放物品。可以发现当要在第$i$行摆放物品时，只会受到第$i-1$行的影响，而$i-1$往上的行不会影响到第$i$行的摆放。因此状态定义时只用记录一行的状态就可以了。
定义状态$f(i,j)$表示所有摆完前$i$行，且第$i$行的状态为$j$的所有摆放方案的集合。根据前一行$(i-1)$的状态$k$来进行划分。
首先$j$的二进制中为$1$的位在当前行是可以摆放的。
然后状态$j$要满足，二进制下的$j$不包含连续的两个$1$，状态$k$同理。
最后$j$和$k$在同一列上（同一数位上）不能同时为$1$，即要满足$j ~\&~ k ~==~ 0$。
因此状态转移方程为$$f(i,j) = \sum\limits_{k=0}^{2^{m}-1} {f(i-1,k)},~~ \text{($k$不存在连续相邻的两个$1$且$j~\&~k==0$)}$$
AC代码如下，时间复杂度为$O(n \times 2^{2m})$：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int N = 15, M = 1 << 12, mod = 1e8;
5
6 int n, m;
7 int f[N][M];
8 int g[N];
9
10 bool check(int x) {
11 for (int i = 1; i < m; i++) {
12 if (x >> i & 1 && x >> i - 1 & 1) return false;
13 }
14 return true;
15 }
16
17 int main() {
18 scanf("%d %d", &n, &m);
19 for (int i = 1; i <= n; i++) {
20 int t = 0; // 把第i行的可种植的状态用二进制表示
21 for (int j = 0; j < m; j++) {
22 int v;
23 scanf("%d", &v);
24 t |= !v << j; // 可种植为0，不可种植为1，因此当j&t==0时j的状态才合法
25 }
26 g[i] = t;
27 }
28
29 f[0][0] = 1; // 第0行摆放物品
30 for (int i = 1; i <= n + 1; i++) {
31 for (int j = 0; j < 1 << m; j++) {
32 if (!(j & g[i]) && check(j)) { // j是合法种植方案，且j不存在连续相邻的两个1
33 for (int k = 0; k < 1 << m; k++) {
34 // 这里可以省略k不存在连续相邻的两个1这个条件是因为，当k不合法时一定有f[i-1][k] = 0
35 if (!(j & k)) f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
36 }
37 }
38 }
39 }
40
41 printf("%d", f[n + 1][0]); // 摆完前n行，此时第n+1行一定没有任何物品
42
43 return 0;
44 }
可以先把合法的状态预处理出来，AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int N = 15, M = 1 << 12, mod = 1e8;
5
6 int n, m;
7 int f[N][M];
8 vector<int> state, st[M];
9
10 bool check(int x) {
11 for (int i = 1; i < m; i++) {
12 if (x >> i & 1 && x >> i - 1 & 1) return false;
13 }
14 return true;
15 }
16
17 int main() {
18 scanf("%d %d", &n, &m);
19
20 for (int i = 0; i < 1 << m; i++) { // 预处理出来不包含连续两个1的状态
21 if (check(i)) state.push_back(i);
22 }
23 for (auto &i : state) {
24 for (auto &j : state) {
25 if ((i & j) == 0) st[i].push_back(j); // 表示状态i可以由j转移过来
26 }
27 }
28
29 f[0][0] = 1;
30 for (int i = 1; i <= n + 1; i++) {
31 int t = 0;
32 for (int j = 0; j < m; j++) {
33 int x;
34 scanf("%d", &x);
35 t |= !x << j;
36 }
37
38 for (auto &j : state) {
39 if ((j & t) == 0) {
40 for (auto &k : st[j]) {
41 f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
42 }
43 }
44 }
45 }
46
47 cout << f[n + 1][0];
48
49 return 0;
50 }
参考资料
AcWing 327. 玉米田（算法提高课）：https://www.acwing.com/video/404/
标签：状态,return,int,玉米田,摆放,15 From： https://www.cnblogs.com/onlyblues/p/16600387.html