POJ 2411 Mondriaan's Dream：狀態壓縮DP經典解法

問題描述

給定 h × w 的矩形（1 ≤ h, w ≤ 11），求用 2 × 1 小矩形完全鋪滿的方案數。輸入以 0 0 結束，對稱方案重複計算。

狀態壓縮DP核心思路

由於 h ≤ 11，可用二進制狀態表示每行的鋪放情況。採用行狀態轉移，dp[i][state] 表示前 i 行處理完且第 i 行狀態為 state 的方案數。目標為 dp[w][0]（最後一行無懸空）。

DFS生成合法轉移

使用 DFS 預計算所有合法的行內鋪放方式，生成 from 和 to 狀態對：

void dfs(int pos, int from, int to) {
    if (pos > n) return;
    if (pos == n) { F1[++num] = from; F2[num] = to; return; }
    dfs(pos + 1, (from << 1) | 1, to << 1);      // 豎放
    dfs(pos + 1, from << 1, (to << 1) | 1);      // 豎放(另一種表示)
    dfs(pos + 2, from << 2, to << 2);            // 橫放
}

DP轉移與滾動數組優化

利用預計算的轉移對進行 DP，空間優化為一維滾動數組：

f[0][0] = 1;
for (int i = 0; i < m; ++i)
    for (int j = 1; j <= num; ++j)
        f[i + 1][F2[j]] += f[i][F1[j]];
// 答案為 f[m][0]

替代方案：檢查狀態合法性

另一種寫法直接枚舉所有狀態，用 C(x) 檢查狀態 x 是否合法（連續 1 的個數為偶數），然後檢查兩行狀態相容性：

bool C(int x) {
    while (x) {
        if (x & 1) { x >>= 1; if (!(x & 1)) return false; x >>= 1; }
        else x >>= 1;
    }
    return true;
}

本題是狀態壓縮DP的經典入門題，關鍵在於正確建模行狀態與轉移關係。