题意:现在有一个由n个字符组成的长度为m的字符串,可以对其通过增加字符或者删除字符来使其变成回文字符串,而增加或者删除字符都有一个花费,求解使该字符串变成回文所进行操作的最小花费. 用dp[start][end]表示使字符串ss[being]……ss[end]变成回文字符串所需的最小花费,只需考虑开始位置和结束位置即可. 1> 如果ss[begin]!=ss[end],那么有四种操作可以使其变成回文: a> 在dp[begin+1][end]处添加或者删除字符ss[begin],所以这两种操作花费为:dp[begin][end]=min{dp[begin+1][end]+add[begin],dp[begin+1][end]+del[begin]} 用cost[begin]表示cost[begin]=min(add[begin],del[begin]),则上述方程可以写成:dp[begin][end]=dp[begin+1]+cost[begin] b> 在dp[begin][end-1]处添加或者删除字符ss[end],所以这两种操作的花费为:dp[begin][end]=dp[begin][end-1]+cost[end] 2> 如果ss[begin]=ss[end],那么有两种情况构成回文数,即字符串保持不变和删除ss[begin]和ss[end],也就是选择dp[begin][end]与dp[begin+1][end-1]中的最小值. 综上所述:状态转移方程为: dp[begin][end]=min{dp[begin+1][end]+cost[begin],dp[begin][end-1]+cost[end]} ss[i]!=ss[j] dp[begin][end]=min{dp[begin][end],dp[begin+1][end-1]} ss[i]=ss[j]#include<iostream> #include<string> #include<algorithm> using namespace std; const int MAXM=2005; int dp[MAXM][MAXM]; int cost[30]; int main() { freopen("1.txt","r",stdin); int i,j,n,m,a,b; char s; string ss; cin>>n>>m; cin>>ss; for(i=0;i<n;i++) { cin>>s>>a>>b; cost[s-'a']=min(a,b); } memset(dp,0,sizeof(dp)); for(j=0;j<m;j++) for(i=j-1;i>=0;i--) { dp[i][j]=min(dp[i+1][j]+cost[ss[i]-'a'],dp[i][j-1]+cost[ss[j]-'a']); if(ss[i]==ss[j]) dp[i][j]=min(dp[i][j],dp[i+1][j-1]); } cout<<dp[0][m-1]<<endl; }
