题目链接：http://pipioj.online/problem.php?id=1096

1. 题意

给定一个长度为 M 的字符串 S。
对每个字母 c，给出：

  • 插入一个 c 的代价 add[c]
  • 删除一个 c 的代价 del[c]

要求把 S 变成回文串，求最小总代价。
可在任意位置进行插入/删除，且有多组数据。

2. 关键观察

对某个字符 c 来说，最终只关心“让它多一个或者少一个”的代价，因此可以先做：

cost[c] = min(add[c], del[c])

后续转移只用 cost 即可。

3. 区间 DP 设计

设 dp[i][j] 表示把子串 S[i..j] 变成回文串的最小代价（1 <= i <= j <= M）。

转移：

  1. 删/补左端字符：dp[i+1][j] + cost[S[i]]
  2. 删/补右端字符：dp[i][j-1] + cost[S[j]]
  3. 若 S[i] == S[j]，两端可直接匹配：dp[i+1][j-1]

所以：

1
2
3
4
5
6
dp[i][j] = min(
  dp[i+1][j] + cost[S[i]],
  dp[i][j-1] + cost[S[j]]
)
if S[i] == S[j]:
  dp[i][j] = min(dp[i][j], dp[i+1][j-1])

初始化：单个字符本身是回文，dp[i][i] = 0。
遍历顺序：i 从大到小，j 从小到大，保证子问题先算好。

复杂度：

  • 时间：O(M^2)（M<=2000 可过）
  • 空间：O(M^2)

4. AC 代码（提交通过）

下面给出提交通过的代码（原样保留）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>

using namespace std;

string str;
int cost[26];
int dp[2010][2010];

int main () {
    //freopen("input1096.txt","r",stdin);
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF) {
        memset(dp,0,sizeof(dp));
        memset(cost,0,sizeof(cost));
        cin >> str;
        str = '#' + str;
        for(int i = 0;i < n;i ++) {
            char c;
            int add;
            int del;
            cin>>c>>add>>del;
            cost[c - 'a' + 1] = min(add,del);
        }
        for(int i = m - 1;i >= 1;i --) {
            for(int j = i + 1;j <= m;j ++) {
                dp[i][j] = min(dp[i + 1][j] + cost[str[i] - 'a' + 1],dp[i][j - 1] + cost[str[j] - 'a' + 1]);
                if(str[i] == str[j]) {
                    dp[i][j] = min(dp[i][j],dp[i + 1][j - 1]);
                }
            }
        }
        printf("%d\n",dp[1][m]);
    }
    return 0;
}

5. 一个小细节

当前代码把字符映射成 1..26，因此 cost 数组更稳妥写成 int cost[27]（或直接用 cost[128] 按 ASCII 存）。
思路和转移本身是完全正确的。