HDU 4628 Pieces 狀態壓縮 DP 最小回文覆蓋

問題描述

給定長度 ≤16 的字符串，每步可刪除一個子序列（不要求連續），只要該子序列是回文。求刪空整個字符串的最少步數。

關鍵觀察

• 長度 ≤16 ⇒ 狀態總數 ≤ 2¹⁶ = 65536，適合狀態壓縮 DP
• 任意單字符均為回文 ⇒ 答案 ≤ 16
• 預計算所有子集是否為回文：ispal[mask]

狀態定義與轉移

dp[mask]：刪除 mask 所代表字符集合所需最少步數。

• 初始 dp[0] = 0，其餘 INF
• 枚舉 mask 從 1 到 (1<
• 若 ispal[mask]，dp[mask] = 1
• 否則枚舉非空真子集 sub ⊂ mask：dp[mask] = min(dp[mask], dp[sub] + dp[mask^sub])

子集枚舉優化

for (int sub = (mask-1) & mask; sub; sub = (sub-1) & mask) {
    if (ispal[sub]) // 可選剪枝
        dp[mask] = min(dp[mask], dp[sub] + dp[mask^sub]);
}

回文預處理

bool isPal(int mask) {
    string t;
    for (int i = 0; i < n; ++i)
        if (mask & (1<<i)) t += s[i];
    for (int i = 0, j = t.size()-1; i < j; ++i, --j)
        if (t[i] != t[j]) return false;
    return true;
}

記憶化搜索寫法（遞歸 + 備忘錄）

int dfs(int mask) {
    if (dp[mask] != INF) return dp[mask];
    if (ispal[mask]) return dp[mask] = 1;
    for (int sub = (mask-1) & mask; sub; sub = (sub-1) & mask)
        if (ispal[sub])
            dp[mask] = min(dp[mask], dfs(sub) + dfs(mask^sub));
    return dp[mask];
}

複雜度分析

• 預處理回文：O(2ⁿ · n) ≈ 10⁶ 操作
• DP 狀態數 2ⁿ，每狀態枚舉子集平均 3ⁿ/2ⁿ = 1.5ⁿ，總體 O(3ⁿ)
• n=16 時 3¹⁶ ≈ 4.3×10⁷，配合剪枝可通過

示例

Input:  abb
子集 {a} {b} {b} 均回文
{a,b,b} 非回文
最優分割：{a} + {b,b} → 2 步