思路：dp[i][j]表示区间i,j变为回文串最少的代价.
#include<map> #include<set> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pb push_back #define mp make_pair #define Maxn 2002 #define Maxm 80002 #define LL __int64 #define Abs(x) ((x)>0?(x):(-x)) #define lson(x) (x<<1) #define rson(x) (x<<1|1) #define inf 0x7fffffff #define Mod 1000000007 using namespace std; int dp[Maxn][Maxn],val[255]; char str[Maxn]; int main() { int n,m,i,j,a,b; char s[5]; while(scanf("%d%d",&n,&m)!=EOF){ scanf("%s",str+1); for(i=1;i<=n;i++){ scanf("%s %d %d",s,&a,&b); val[s[0]]=min(a,b); } for(i=1;i<=m;i++){ for(j=i-1;j>=1;j--){ if(str[i]==str[j]){ dp[j][i]=dp[j+1][i-1]; } else{ dp[j][i]=min(dp[j+1][i]+val[str[j]],dp[j][i-1]+val[str[i]]); } } } printf("%d ",dp[1][m]); } return 0; }