我自闭了，调了一下午，我居然认为 (2, 3) 凑不出 (7)，我怕是个孤儿。
这是一位非要用二进制写的勇士。
首先定义状态 (S)，若 (S) 的二进制第 (k) 位为 (1) 表示那一位下是空闲可以填数的。
再定义一个 (S(x)) 表示 (S) 下第 (x) 位的值。
显然填 (2 * 3) 小方格的时候，能不能填取决于最近的三行，和前面无关，我们搞一个二维二进制，通过转移达到目的。
$f[i][j][k] $ 为前 (i) 行，第 $ i$ 行状态为 (j)，第 (i - 1) 行状态为 (k) 填的最多的小方格数。为什么要用空闲的状态状压而不是填过的呢？因为如果用填过的你不知道在上一行是不是已经填完了。。
转移 (f[i][j][k] = max( f[i - 1][p][q] + val(p, q, j, k)))。(val(p, q, j, k)) 是两行状态转移的中，以 (i) 行为
最下方填写的方格数。
显然复杂度爆炸，我们需要的是，压状态！压、压再压！！由于这是一个最优问题，所以我们可以剪枝，即保留的状态当且仅当里面的 (1) （空闲位置）全部放上小方块，以这个原则进行剪枝，可以大大降低复杂度
-
对于一个状态 (k, j) 考虑压掉不合法的状态
- (k(x) = 1, j(x) = 0) 那个一永远放不上小方块
- (k(x) = 1, j(x) = 1) 连续数量必须为偶数，因为到了 (2) 个空闲还没扔掉意味着一定是要跨三行，这样列只能 (2) 个。
- (k(x) = 0, j(x) = 1) 连续数量必须 (> 1)
当 (m = 10) 最坏情况下，合法的 (k, j) 数量只有 (1123) 个。
-
接着考虑合法的 (q, p) → (k, j) 的转移以及计算 (val)
转移的实质就是在 (j) 这一行放可行的方块。
- 如果 (p(x) = k(x)) 说明没放新的块，这种情况必须进行续传：
- (p(x) = k(x) = 1) 的情况，如果这时候 (q) 必须是 (0)，(j) 必须是 (1)（不能积累3个空闲块）
- 否则说明放了新的块
- (p(x) = 0, k(x) = 1)，无中生有可还行（减掉
- (q(x) = 0, p(x) = 1, k(x) = 0)，这时候 (j(x)) 必须为 (0) 并且连续块是 (3) 的倍数（即放横着的块，贡献+）
- (q(x) = 1, p(x) = 1, k(x) = 0) 这时候 (j(x)) 必须为 (0) 且是偶数（放竖着的块，贡献+）
- 如果 (p(x) = k(x)) 说明没放新的块，这种情况必须进行续传：
这样可以的匹配一共有 (5477) 个（在 (m = 10) 下）
跑的还是很快的 (740ms)
#include <cstdio>
#include <iostream>
#include <cstring>
#define x first
#define y second
using namespace std;
const int N = 150, S = 1130, M = 10, L = 5500;
typedef pair<int, int> PII;
int n, m, K, tot, cnt, o, f[N + 1][S], g[N + 1];
PII s[S];
struct Node{
int a, b, c, y;
} d[L];
bool check(int k, int j) {
int c1 = 0, c2 = 0;
for (int i = 0; i < m; i++) {
if ((k >> i & 1) && !(j >> i & 1)) return false;
if ((k >> i & 1) && (j >> i & 1)) c2++;
else {
if (c2 & 1) return false;
c2 = 0;
}
if (!(k >> i & 1) && (j >> i & 1)) c1++;
else {
if (c1 == 1) return false;
c1 = 0;
}
}
return !(c2 & 1) && (c1 != 1);
}
int get(int q, int p, int k, int j) {
o = 0;
int res = 0;
for (int i = 0; i < m; i++) {
if ((p >> i & 1) && (k >> i & 1)) {
if (q >> i & 1 || i + 1 >= m) return -1;
int u = i + 1;
if ((q >> u & 1) || !(p >> u & 1) || !(k >> u & 1)) return -1;
i = i + 1;
}
if (!(p >> i & 1) && (k >> i & 1)) return -1;
if (!(q >> i & 1) && (p >> i & 1) && !(k >> i & 1)) {
if ((j >> i & 1) || i + 2 >= m) return -1;
o |= 1 << i;
res++;
for (int u = i + 1; u <= i + 2; u++) {
o |= 1 << u;
if ((q >> u & 1) || !(p >> u & 1) || (k >> u & 1) || (j >> u & 1)) return -1;
}
i = i + 2;
}
if ((q >> i & 1) && (p >> i & 1) && !(k >> i & 1)) {
if ((j >> i & 1) || i + 1 >= m) return -1;
res++;
o |= 1 << i;
int u = i + 1;
o |= 1 << u;
if (!(q >> u & 1) || !(p >> u & 1) || (k >> u & 1) || (j >> u & 1)) return -1;
i = i + 1;
}
}
return res;
}
bool judge(int i, int s) {
if (i < 1) return true;
return !(s & g[i]);
}
int main() {
int T; scanf("%d", &T);
while (T--) {
cnt = tot = 0;
memset(g, 0, sizeof g);
scanf("%d%d%d", &n, &m, &K);
for (int i = 1, x, y; i <= K; i++) {
scanf("%d%d", &x, &y); g[x] |= 1 << (y - 1);
}
for (int j = 0; j < (1 << m); j++) {
for (int k = 0; k < (1 << m); k++) {
if (check(k, j)) s[tot++] = make_pair(j, k);
}
}
for (int i = 0; i < tot; i++) {
for (int j = 0; j < tot; j++) {
int res = get(s[i].y, s[i].x, s[j].y, s[j].x);
if (res != -1) {
d[cnt++] = (Node) { j, i, res, o};
}
}
}
memset(f, 0xcf, sizeof f);
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < cnt; j++) {
if (!judge(i - 2, s[d[j].b].y) || !judge(i - 1, s[d[j].b].x) || !judge(i - 1, s[d[j].a].y) || !judge(i, s[d[j].a].x | d[j].y)) continue;
if (f[i - 1][d[j].b] < 0) continue;
f[i][d[j].a] = max(f[i][d[j].a], f[i - 1][d[j].b] + d[j].c);
}
}
printf("%d
", f[n][0]);
}
}