题目传送门
题目大意
给定一个 \(N\times M\) 的网格，求用 \(1\times 2\) 和 \(2\times 1\) 的长方形去铺满它有多少种方案。
数据范围：\(N,M\le 11\)。
思路：
考虑怎么放才能刚好填满网格。
可以想到，如果先放横着的，再放竖着的，那么当我们将横着的都放完后，若竖着的恰好能刚好嵌进去，说明这是一个合法方案。
也就是说，放完横着的矩形后放竖着的矩形的方法的唯一确定的，那么：
求总的方案数其实就是求横着放且合法（使竖着的能嵌进去刚好铺满网格）的方案数。
因为放横着的矩形时拓展的方向是横向的，就是说我们放矩形时，当前放的这个矩形只影响到下一列，这启示我们将“列号”作为 dp 的阶段，同时由于上一列的放置情况会影响到当前这一列，所以我们需要将上一列伸出来的部分作为状态中的一维才能转移。
那么如何表示上一列那些地方伸出来了呢？
如果用 bool 数组来表示第 \(i\) 行有没有伸出来，不仅效率低下，而且不方便计算，这时候状态压缩就来了：采用二进制压缩，相当于将原来的 bool 数组变成一个二进制数 \(state\)，\(state\) 的第 \(i\) 位表示第 \(i\) 是否伸出，\(0\) 表示未伸出，\(1\) 表示伸出。
设 \(f(i, state)\) 表示已经摆完了前 \(i - 1\) 列，且从第 \(i - 1\) 列伸到第 \(i\) 列的方案数，那么状态转移方程为：
\[f(i, state) = \sum f(i - 1, last\_state) \]其中 \(last\_state\) 是第 \(i - 2\) 列伸到第 \(i - 1\) 的状态，且需要满足 \(last\_state\) 对于 \(state\) 合法。
\(last\_state\) 对于 \(state\) 合法当且仅当以下两个条件满足：
- \(state \wedge last\_state = 0\)，即第 \(i - 2\) 列伸到第 \(i - 1\) 的小方格和 \(i - 1\) 列放置的小方格不重复；
- 每一列，所有连续着空着的小方格必须是偶数个，因为竖着的矩形必须要能嵌入。
初始化： \(f(0,0) = 1\)。
按定义这里是：前第 \(-1\) 列都摆好，且从第 \(-1\) 列到第 \(0\) 列伸出来的状态为 \(0\) 的方案数。
首先，这里没有 \(-1\) 列，最少也是 \(0\) 列。
其次，没有伸出来，即没有横着摆的。即这里第 \(0\) 列只有竖着摆这 \(1\) 种状态。
目标： \(f(m,0)\)。
\(f(m, 0)\) 表示前 \(m - 1\) 列都处理完，并且第 \(m - 1\) 列没有伸出来的所有方案数。
即整个棋盘处理完的方案数。
再用集合划分的思想来解释一下。
首先要 “化零为整”，即用一个集合表示一类情况，对于这道题，假设我们放矩形时是对于每列都从上往下放，那么可以根据当前放到了第几列来划分集合。
但这样划分我们无法找到各个集合之间的转移关系，所以还要再划分一次。
集合划分的依据就是寻找集合中元素的不同点，发现在摆完前 \(i - 1\) 列的方案中向第 \(i\) 列伸出的情况不同，所以可以以此来划分。
所以状态表示为：\(f(i, state)\) 表示已经摆完了前 \(i - 1\) 列，且从第 \(i - 1\) 列伸到第 \(i\) 列的方案数。
接着就是 “化整为零” 的过程，即状态计算，同上。
\(\texttt{Code:}\)
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 12, M = 1 << N;
typedef long long ll;
int n, m;
vector<int> tran[M];
ll dp[N][M];
bool st[M];
bool check(int x) { //判断该状态是否满足所有连续着空着的小方格必须是偶数个
int cnt = 0;
for(int i = 0; i < n; i++) {
if(x >> i & 1) {
if(cnt & 1) return false;
cnt = 0;
}
else ++cnt;
}
if(cnt & 1) return false;
return true;
}
int main() {
while(scanf("%d%d", &n, &m), n || m) {
for(int i = 0; i < 1 << n; i++) st[i] = check(i); //提前预处理那哪些状态是合法的
for(int i = 0; i < 1 << n; i++) {
tran[i].clear(); //多测清空
for(int j = 0; j < 1 << n; j++)
if(!(i & j) && st[i | j])
tran[i].push_back(j); //提前预处理出每个可行状态能由那些状态转移过来
}
memset(dp, 0, sizeof dp);
dp[0][0] = 1;
for(int i = 1; i <= m; i++)
for(int j = 0; j < 1 << n; j++)
for(int k = 0; k < tran[j].size(); k++)
dp[i][j] += dp[i - 1][tran[j][k]];
printf("%lld\n", dp[m][0]);
}
return 0;
}