题目链接：
题目分析：
玄学(dp)
设(val[s[i] - 'a' + 1])表示字母(s[i])的花费
首先发现对于一个已经回文了的串(s[i, j])，在(s[i - 1])的位置上删去和在(s[j + 1])的位置上加上本质上是一样的，所以(val[s[i] - 'a' + 1])直接取增删的最小即可
设(dp[i][j])表示把(s[i, j])变成回文串的最小代价，初始化所有花费为(INF)，(dp[i][i] =0)，如果有(s[i] == s[i + 1])，那么有(dp[i][j + 1] = 0)
然后是玄学的转移方程，稍微分情况讨论一下：
- 若有(s[i - 1] == s[j + 1])，则(dp[i - 1][j + 1] = min(dp[i - 1][j + 1], dp[i][j]))
- (dp[i - 1][j] = min(dp[i - 1][j], dp[i][j] + val[s[i - 1] - 'a' + 1]))
- (dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + val[s[j + 1] - 'a' + 1]))
答案即为(dp[1][m])
代码：
#include<bits/stdc++.h>
#define N (2000 + 10)
using namespace std;
inline int read() {
int cnt = 0, f = 1; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + c - '0'; c = getchar();}
return cnt * f;
}
const int INF = 1000000000 + 7;
int n, m, x, y;
char s[N], c;
int val[30], dp[N][N];
int main() {
n = read(), m = read();
scanf("%s", s + 1);
for (register int i = 1; i <= n; i++) {
cin >> c;
x = read(), y = read();
val[c - 'a' + 1] = min(x, y);
}
for (register int i = 0; i <= m; ++i)
for (register int j = 0; j <= m; ++j) dp[i][j] = INF;
for (register int i = 1; i <= m; i++) {
dp[i][i] = 0;
if (s[i] == s[i + 1]) dp[i][i + 1] = 0;
}
for (register int l = 0; l <= m; ++l)
for (register int i = 1; i <= m; ++i) {
int j = i + l;
if (s[i - 1] == s[j + 1]) dp[i - 1][j + 1] = min(dp[i - 1][j + 1], dp[i][j]);
dp[i - 1][j] = min(dp[i - 1][j], dp[i][j] + val[s[i - 1] - 'a' + 1]);
dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + val[s[j + 1] - 'a' + 1]);
}
printf("%d", dp[1][m]);
return 0;
}