Ural 1152 False Mirrors 狀壓 DP 詳解
這是一道經典的狀態壓縮動態規劃題目。給定 n ≤ 21 個數字，需計算某種操作的最小代價。核心在於用二進制位掩碼表示集合狀態，dp[mask] 表示狀態 mask 的最小代價。
關鍵技術點
- 位運算優先級陷阱：四則運算優先級高於位運算，混合使用時必須加括號。例如
i & (1 << j - 1) 需寫成 i & (1 << (j - 1))，否則會先算減法導致錯誤。
- 狀態轉移：從全集狀態
(1< 向空集 0 轉移，枚舉每個可移除元素及其相鄰影響。
- 預計算子集和：
sum[mask] 存儲該狀態包含元素的值總和，加速轉移計算。
核心代碼片段
for (int i = (1<= 1; i--) {
for (int j = 0; j < n; j++) if (i & (1<
經驗總結
狀壓 DP 核心是位運算技巧，調試時建議列印關鍵狀態驗證位運算正確性。對於 n ≤ 21，狀態數 2^21 ≈ 200 萬，時間複雜度 O(n 2^n) 在優化後可通過。
