POJ 2411 Mondriaan's Dream：狀壓 DP 填充矩形計數

POJ 2411「Mondriaan's Dream」：h×w 矩形 (h,w ≤ 11)，用 2×1 骨牌鋪滿（可橫放、豎放），求方案數。本文解析輪廓線狀壓 DP（插頭 DP 前身）：逐行狀態轉移，DFS 生成合法狀態。

狀態定義

逐行掃描，狀態表示當前行與下一行的邊界連接關係。
用二進制 w 位表示：第 j 位 = 1 表示第 j 列向下延伸了一塊豎放骨牌（佔據下一行該位置）。

狀態轉移：DFS 生成下一行狀態

在當前行位置 pos (0..w-1)，根據上一行狀態 pre 和當前行已放置情況 cur，嘗試放置：

• 若 pre 第 pos 位 = 1：上方有豎牌延伸下來，當前位置已被佔用，必須在 cur 置 1（繼續向下延伸）或置 0（豎牌結束）。但標準輪廓線 DP 中，pre 位=1 表示上一行已放豎牌佔據當前位置，當前行該位置已填滿，直接跳到下一位，cur 該位=0（因骨牌已結束）。
• 若 pre 位 = 0：當前位置空閒，可選：
• 放橫牌：佔據 pos 和 pos+1，要求 pos+1 < w 且 pre 第 pos+1 位 = 0。
• 放豎牌：佔據當前位置並向下延伸，cur 第 pos 位 = 1。

標準 DFS 參數

• pos：當前列 (0..w)
• pre：上一行狀態 (w 位)
• cur：正在構建的當前行狀態
• next：下一行狀態（即豎牌延伸標記）

完整代碼（C++）

#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;
const int MAXH = 12;
LL dp[MAXH][1<<11];
int h, w, fullMask;

void dfs(int pos, int pre, int cur, int next) {
    if (pos == w) {
        dp[cur][next] += dp[cur-1][pre]; // 注意：此處行號需調整
        return;
    }
    if (pre & (1<

修正後的標準實現
#include 
#include 
using namespace std;
typedef long long LL;
LL dp[12][1<<11];
int h, w;

void dfs(int row, int col, int pre, int nxt) {
    if (col == w) {
        dp[row][nxt] += dp[row-1][pre];
        return;
    }
    if (pre & (1<

複雜度

狀態數：2^w ≤ 2^11 = 2048。
每行每狀態 DFS 分支 ≤ 2，總轉移 O(h × 2^w × w) ≈ 11 × 2048 × 11 ≈ 2.5×10⁵。
極快，記憶體 ~12 × 2048 × 8 bytes ≈ 200KB。


關鍵細節

交換 h,w 使 w 最小：狀態數指數級依賴 w，優先縮小 w。
初始狀態：dp[0][fullMask] = 1 表示第 0 行「虛擬」全有豎牌向下延伸，使第 1 行完全空閒可自由放置。
最終狀態：dp[h][fullMask] 表示第 h 行後無豎牌延伸（即鋪滿）。
DFS 參數：pre 為上一行狀態（只讀），nxt 為構建的下一行狀態（寫入）。


總結
本題是「輪廓線狀壓 DP」的入門經典。核心思想：逐行掃描，狀態記錄「向下延伸的豎牌位置」，DFS 在行內嘗試所有合法放置方式生成下一行狀態。此模板可直接推廣至「多米諾骨牌鋪滿」、「矩形分割」、「網格圖哈密頓路徑」等問題。掌握「狀態含義、DFS 分支、初始/終止條件」三要素即可舉一反三。