BZOJ 1710 [Usaco2007 Open] Cheappal 廉價回文 —— 區間 DP 最小編輯代價構造回文

BZOJ 1710：給定長度 M ≤ 2000 的字串，每種字符有「添加代價」與「刪除代價」。可在任意位置添加/刪除字符，求將字串變為回文的最小總代價。空串合法。

一、代價等價轉化

「在左端添加 c」等價於「在右端刪除 c」，代價取 min(add[c], del[c])。
令 w[c] = min(add[c], del[c])，問題簡化為：刪除字符代價為 w[c]，求最小刪除代價使剩餘字串為回文。

二、區間 DP

f[i][j] = 將 s[i..j] 變為回文的最小代價（1-based）。

轉移：

// 刪除左端 或 刪除右端
f[i][j] = min(f[i+1][j] + w[s[i]], f[i][j-1] + w[s[j]]);

// 兩端字符相同，可保留
if (s[i] == s[j]) f[i][j] = min(f[i][j], f[i+1][j-1]);

初始化：f[i][i] = 0（單字符本身回文），f[i][i-1] = 0（空串）。

按長度遞增 DP：

for (int len = 2; len <= n; ++len)
    for (int i = 1; i+len-1 <= n; ++i) {
        int j = i+len-1;
        f[i][j] = min(f[i+1][j] + w[s[i]], f[i][j-1] + w[s[j]]);
        if (s[i] == s[j]) f[i][j] = min(f[i][j], f[i+1][j-1]);
    }

三、完整 AC 代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
char s[MAXN];
int w[26], f[MAXN][MAXN];

int main() {
    int n, m; scanf("%d%d", &n, &m);
    scanf("%s", s+1);
    for (int i = 1; i <= n; ++i) {
        char ch; int add, del;
        scanf(" %c%d%d", &ch, &add, &del);
        w[ch-'a'] = min(add, del);
    }
    memset(f, 0, sizeof(f));
    for (int len = 2; len <= m; ++len) {
        for (int i = 1; i+len-1 <= m; ++i) {
            int j = i+len-1;
            f[i][j] = min(f[i+1][j] + w[s[i]-'a'], f[i][j-1] + w[s[j]-'a']);
            if (s[i] == s[j]) f[i][j] = min(f[i][j], f[i+1][j-1]);
        }
    }
    printf("%d\n", f[1][m]);
    return 0;
}

四、樣例驗證

Input:
3 4
abcb
a 1000 1100
b 350 700
c 200 800

w: a=1000, b=350, c=200
DP 過程：
f[1][4] = min(f[2][4]+1000, f[1][3]+350) = min(200+1000, 200+350) = 550? 實際最優是保留 bcb (刪除 a 代價 1000) 或 兩側加 b,c,b (350+200+350=900)。
正確答案 900。代碼輸出 900。

五、複雜度

• 時間：O(M²) = 4×10⁶，M=2000 瞬間通過。
• 空間：O(M²) = 16 MB int，可優化至 O(M) 滾動數組（但 M=2000 無需）。

六、關鍵洞察

1. 添加/刪除對稱性 → 統一為刪除代價 w[c] = min(add, del)。
2. 區間 DP 經典模型：f[i][j] 從兩端向中間縮減，保留相同字符無代價。