题意
给出小写字母组成的字串，要求增删字母使其变为回文串，增删不同字母的花费不同，求最小花费
数据范围：$1 \le L \le 2000$
题解
用$f[i][j]$表示将区间$[i,j]$修改为回文串的最小花费，显然有$$f[i][i]=0$$
当$s[i]=s[i+1]$时有$$f[i][i+1]=0$$
因为要从小区间转移到大区间，$f[i][j]$可以从$f[i+1][j]$或$f[i][j-1]$转移而来，或在满足$s[i]=s[j]$时从$f[i+1][j-1]$转移而来，而此时这三个区间已被修改为回文串
考虑区间$[i+1][j]$，可以选择在区间$[i][j]$左侧删去$s[i]$，或在区间$[i][j]$右侧增添$s[i]$，这两种操作效果相同，因此可以选择这两种操作中花费最少的（可预处理）
区间$[i][j-1]$同理
状态转移方程如下
$$ f[i][j]= \left\{ \begin{aligned} & f[i+1][j-1],s[i]=s[j] \\ & f[i+1][j]+val[s[i]] \\ & f[i][j-1]+val[s[j]] \\ \end{aligned} \right. $$
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=26+1;
const int M=2000+10;
int n,m,a,b;
char s[M],c[1];
int v[N];
int dp[M][M];
template <typename T>
inline T Min(T a,T b){
return a<b?a:b;
}
int main(){
scanf("%d%d",&n,&m);
scanf("%s",s+1);
for(int i=1;i<=n;i++){
scanf("%s%d%d",c,&a,&b);
v[c[0]-'a']=Min(a,b);
}
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=m;i++){
dp[i][i]=0;
if(s[i]==s[i+1])
dp[i][i+1]=0;
}
for(int l=0;l<=m;l++)
for(int i=1,j=l+1;j<=m;i++,j++){
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]+v[s[i-1]-'a']);
dp[i][j+1]=Min(dp[i][j+1],dp[i][j]+v[s[j+1]-'a']);
}
printf("%d",dp[1][m]);
return 0;
}