POJ 3254 Corn Fields 状态压缩DP（铺砖问题）

一、题目大意

我们要在N * M的田地里种植玉米，有如下限制条件：

1、对已经种植了玉米的位置，它的四个相邻位置都无法继续种植玉米。

2、题目中有说一些块无论如何，都无法种植玉米。

求所有种植玉米的方案数（不种植也是一种方案）

二、解题思路

不难看出本题目是铺砖问题，我们可以先写一个基于递归解决的Domo。

可以定义数组color[i][j]代表该位置是否起初就无法种植

并定义数组used[i][j]代表该位置是否已经被旁边的块覆盖，无法种植。

对于i j 位置，判断它如果不能种植，就直接计算下一个位置。

如果可以种植，则分别尝试种植和不种植两种情况，将计算出的方案数求和。

写出递归代码如下：

int rec(int i, int j)
{if (i == n){return 1;}if (j == m){return rec(i + 1, 0);}if (color[i][j] || used[i][j]){return rec(i, j + 1);}int res = 0;bool rt = false, dn = false;if (j + 1 < m){rt = used[i][j + 1];}if (i + 1 < n){dn = used[i + 1][j];}res += rec(i, j + 1);used[i][j] = true;if (j + 1 < m){used[i][j + 1] = true;}if (i + 1 < n){used[i + 1][j] = true;}res += rec(i, j + 1);used[i][j] = false;if (j + 1 < m){used[i][j + 1] = rt;}if (i + 1 < n){used[i + 1][j] = dn;}return res;
}

这个递归代码一定是超时的，那么接下来考虑如何把它转成DP，我们发现这个递归算法是从左上一直算到右下，那么对于i j位置，其实只需要记录 (row==i+1&&col<j)和(row==i&&col>=j)的一排元素是否可以种植玉米即可，如下图所示。

所以不难看出，对于同一个位置，且这一排元素确定时，算出的方案数也是确定的，那么我们就可以从右下角开始，一点点边计算边循环到左上角。

在这个计算的过程中，和递归一样，只需要考虑两点。

第一，如果i j位置不能种植玉米，则加上i j位置不种植时的下一块的值 crt[ S 去掉第 j 块 ]。

第二，如果i j位置能够种植玉米，则依次加上i j位置种植和不种植情况时下一块的值，dp[S] 和 crt[S 加上第 j 块 和 第 j+1 块]（如果j+1==m，则不用添加第j+1块）。

初始化时，考虑到最后一块的情况，如果它能够种植，则是2，如果不能则是1，那么就可以初始化DP数组上一行的所有元素为1。

可以使用滑动数组求解，循环计算每一块，之后本次的当前行作为下次计算的上一行即可。

最终输出的答案为上一行的第一个位置。

三、代码

#include <iostream>
using namespace std;
const int MAX_M = 12;
const int MAX_N = 12;
int dp[2][1 << MAX_M];
bool color[MAX_N][MAX_M];
int n, m;
void solve()
{int *crt = dp[0], *next = dp[1];fill(crt, crt + (1 << MAX_M), 1);for (int i = n - 1; i >= 0; i--){for (int j = m - 1; j >= 0; j--){for (int used = 0; used < (1 << m); used++){if (color[i][j] || (used >> j & 1)){next[used] = crt[used & ~(1 << j)];}else{int res = crt[used];if (j + 1 < m){res += crt[used | (1 << (j + 1)) | (1 << j)];}else{res += crt[used | (1 << j)];}next[used] = res % 100000000;}}swap(next, crt);}}printf("%d\n", crt[0]);
}
int main()
{scanf("%d%d", &n, &m);int num;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){scanf("%d", &num);color[i][j] = num == 0;}}solve();return 0;
}

四、相关文献

《挑战程序设计竞赛（第二版）》P196-P198 铺砖问题