我不会区间 dp。
设 \(f_{i,j}\) 表示使得区间 \([i,j]\) 为回文串的最小操作代价，\(cost_{i,j}\) 表示字母 \(i\) 删除/添加的耗费，那么显而易见的，我们有：
- \(f_{i,j} \to \min(f_{i,j-1}+\min(cost_{s_j,0},cost_{s_j,1}),f_{i+1,j}+\min(cost_{s_i,0},cost_{s_i,1}))\)。
- 当 \(s_i=s_j\) 时，\(f_{i,j} \to \min(f_{i,j},f_{i+1,j-1})\)。
注意到当 \(s_i=s_j\) 且 \(i+1=j\) 时，我们的 \(f\) 会出现取到了左端点大于右端点的情况，因此会锅，所以我们要提前处理长度为 \(2\) 的回文。
状态数为 \(O(m^2)\)，转移 \(O(1)\)，时间复杂度 \(O(m^2)\)。
点击查看代码
#include<bits/stdc++.h>
#define int ll
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define inn(i,n,a) For(i,1,n) a[i]=read();
#define ll long long
#define i128 __int128
using namespace std;
inline int read() {
int xx= 0;int f= 1;
char c = getchar();
while(c<'0'||c>'9') {
if(c=='-') f= -1;
c= getchar();
}
while(c>='0'&&c<='9') {
xx= (xx<<1)+(xx<<3)+(c^48);
c= getchar();
}
return xx*f;
}
#define maxn 2030
int n,m;
string s;
int cst[30][5];
int f[maxn][maxn];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n>>m;
cin>>s;
s=' '+s;
For(i,1,n) {
char ch;
cin>>ch;
ch=ch-'a';
cin>>cst[ch][0]>>cst[ch][1];
}
mem(f,0x3f);
For(i,1,n) f[i][i]=0;
For(i,1,n-1) if(s[i]==s[i+1]) f[i][i+1]=0;
For(len,1,m) {
For(i,1,m) {
if(i+len>m) break;
int j=i+len;
f[i][j]=min(f[i][j],f[i][j-1]+min(cst[s[j]-'a'][0],cst[s[j]-'a'][1]));
f[i][j]=min(f[i][j],f[i+1][j]+min(cst[s[i]-'a'][0],cst[s[i]-'a'][1]));
if(s[i]==s[j]) f[i][j]=min(f[i][j],f[i+1][j-1]);
}
}
cout<<f[1][m];
}