题意
有一个字串 \(S\) 长 \(M\)，由 \(N\) 个小写字母构成。欲通过增删字母将其变为回文串，增删特定字母花费不同，求最小花费。
分析
定义状态 \(dp[i][j]\) 表示使 \(i\) 到 \(j\) 这一段区间变成回文串所需要的最小代价。
显然，\(dp[i][j]\) 只能由 \(dp[i + 1][j]\) 或 \(dp[i][j - 1]\) 转移过来，因为两个回文串拼接在一起是不合法的。
然后转移的时候把应消耗的代价加入即可。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 5;
char b,s[MAXN];
int n,m,dp[MAXN][MAXN],c[30][2];
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; i++){
cin >> b;
s[i] = b;
}
memset(dp,0x3f3f3f3f,sizeof dp);
for(int i = 1; i <= n; i++){
cin >> b;
//scanf("%s",&b);
cin >> c[b - 'a'][0] >> c[b - 'a'][1];
}
for(int i = 0; i <= m + 1;++i){
dp[i][i] = 0;
for(int j = 0;j < i;++j)dp[i][j]=0;
}
for(int l = 1; l <= m; l++) {
for(int i = 1; i + l <= m; i++){
int j = i + l;
dp[i][j] = min(dp[i][j],dp[i + 1][j] + min(c[s[i] - 'a'][1],c[s[i] - 'a'][0]));
dp[i][j] = min(dp[i][j],dp[i][j - 1] + min(c[s[j] - 'a'][1],c[s[j] - 'a'][0]));
if(s[i] == s[j]){
if(j - i == 1)dp[i][j] = 0;
else dp[i][j] = min(dp[i][j],dp[i + 1][j - 1]);
}
//cout << dp[i][j] << "\n";
}
}
cout << dp[1][1];
}