問題描述
在 n × m 的棋盤上放 1×2 的多米諾骨牌，不重疊、不超界，求鋪滿棋盤的方案數。n ≤ 15, m ≤ 12。
狀態定義
按行進行 DP。每行狀態用 m 位二進制數表示：1 代表該格被上一行的豎向骨牌佔用，0 代表空閒。
dp[i][mask] 表示前 i 行已填滿，第 i 行狀態為 mask 的方案數。
合法狀態預處理
一行內部必須能用橫向骨牌（佔 2 格）完美填補 0 的位置。即 mask 的二進制中，連續 0 的長度必須為偶數。預處理 valid[mask] 判斷合法性。
狀態轉移
第 i 行狀態 cur 由第 i-1 行狀態 pre 轉移而來，條件：
(cur | pre) == (1<：兩行無空格遺漏。valid[cur & pre]：重疊位置（即豎向骨牌）在 cur 中形成合法的連續段。
轉移方程：dp[i][cur] += dp[i-1][pre]。
代碼實現（C++）
#include
using namespace std;
typedef long long ll;
ll dp[16][1<<12];
bool valid[1<<12];
int n, m, full;
bool check(int mask) {
int cnt = 0;
for (int i = 0; i < m; ++i) {
if (mask & (1<> n >> m, n || m) {
full = (1<
複雜度
- 狀態數：2¹² = 4096。
- 轉移：O(n × 4096²) ≈ 2.5×10⁸，實測 < 1s（C++ 優化後）。
- 可用「按合法狀態列表轉移」進一步優化。
總結
本題是「輪廓線 DP」/「插頭 DP」的簡化版，展示了狀態壓縮 DP 處理鋪磚問題的標準套路：逐行掃描 + 二進制狀態 + 合法性預處理 + 狀態兼容性判斷。掌握此模板，可解決 POJ 2411、HDU 1693 等經典問題。
