题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4804
题目大意
给你一个 \(n \times m\) 的矩形区域。你需要用 \(1 \times 1\) 和 \(1 \times 2\) 的砖块铺满这个区域，且满足如下要求：
- 所有的砖块可以竖着放或横着放；
- 砖角要放在格点上；
- \(1 \times 1\) 的砖不能少于 \(C\) 块也不能多于 \(D\) 块， \(1 \times 2\) 的砖没有数量限制。
- 有些方格在一开始就已经被填充了，这些方格不能被任何砖块覆盖。（在输入里用 0 表示这样的方格，用 1 表示普通方格）
请问有多少种满足上述规则的方案可以将矩形区域铺满？
解题思路
轮廓线动态规划，首先将状态压缩，1 表示这个格子现在被覆盖了， 0 表示没有被覆盖，这样可以把当前考虑的轮廓线上的 \(m\) 列的情况压缩成一个整数，然后按照这一回放什么砖、怎么放进行转移。
状态 \(f[now][s][k]\) 表示：当前位置（\(now\) 能够描绘出行号和列号，以滚动数组实现），以当前位置结尾的不确定状态为 \(s\) ，并且已经放了 \(k\) 个 \(1 \times 1\) 的砖块的方案总数。
进行完轮廓线DP后，答案即为 \(\sum_{i=C}^{D} f[now][(1<<m)-1][i]\) 。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
int n, m, C, D;
long long f[2][1<<11][22];
char maze[101][11];
int main() {
while (~scanf("%d%d%d%d", &n, &m, &C, &D)) {
for (int i = 0; i < n; i ++) scanf("%s", maze[i]);
memset(f[0], 0, sizeof(f[0]));
int now = 0;
f[0][(1<<m)-1][0] = 1;
for (int i = 0; i < n; i ++) { // 遍历行号i
for (int j = 0; j < m; j ++) { // 遍历列号j
now = now ^ 1;
memset(f[now], 0, sizeof(f[now]));
for (int k = 0; k <= D; k ++) { // 遍历放置前已放置1x1砖块个数k
for (int s = 0; s < (1<<m); s ++) { // 遍历放置前不确定点状态
int s2, k2;
/** 当前格子不能放 */
if (maze[i][j] == '0') {
if (s & (1<<(m-1))) { // 最前面格子也放了
s2 = (s<<1)^1, k2 = k;
s2 &= (1<<m)-1;
f[now][s2][k2] += f[now^1][s][k];
f[now][s2][k2] %= MOD;
}
}
/** 当前格子可以放 */
else { // maze[i][j] == '1'
/** 情况1：当前格子不放 */
if (s & (1<<(m-1))) {
s2 = (s<<1), k2 = k;
s2 &= (1<<m)-1;
f[now][s2][k2] += f[now^1][s][k];
f[now][s2][k2] %= MOD;
}
/** 情况2：当前格子放一个竖着2x1的砖块 */
if (i > 0 && !(s & (1<<(m-1)))) {
s2 = (s<<1)^1, k2 = k;
s2 &= (1<<m)-1;
f[now][s2][k2] += f[now^1][s][k];
f[now][s2][k2] %= MOD;
}
/** 情况3：当前格子放一个横着1x2的砖块 */
if (j > 0 && !(s & 1) && (s & (1<<(m-1)))) {
s2 = (s<<1)^3, k2 = k;
s2 &= (1<<m)-1;
f[now][s2][k2] += f[now^1][s][k];
f[now][s2][k2] %= MOD;
}
/** 情况4：当前格子放一个1x1的砖块 */
if ( k < D && (s & (1<<(m-1))) ) {
s2 = (s<<1)^1, k2 = k+1;
s2 &= (1<<m)-1;
f[now][s2][k2] += f[now^1][s][k];
f[now][s2][k2] %= MOD;
}
}
}
}
}
}
long long ans = 0;
for (int i = C; i <= D; i ++) {
ans = (ans + f[now][(1<<m)-1][i]) % MOD;
}
printf("%lld\n", ans);
}
return 0;
}