题意：给你m个字符，其中有n种字符，每种字符都有两个值，分别是增加一个这样的字符的代价，删除一个这样的字符的代价，让你求将原先给出的那串字符变成回文串的最小代价。
思路：区间DP，dp[i][j]代表将区间[i,j]变为回文串的最小代价。
#include#include #include #include #include #include #include #define MAXSIZE 2005#define LL long long#define INF 0x3f3f3f#define mod 10056using namespace std;/*给你m个字符，其中有n种字符，每种字符都有两个值，分别是增加一个这样的字符的代价，删除一个这样的字符的代价，让你求将原先给出的那串字符变成回文串的最小代价。*/int dp[MAXSIZE][MAXSIZE],a[MAXSIZE],add[MAXSIZE],red[MAXSIZE],n,m;char s[MAXSIZE];int Solve(){ memset(dp,0,sizeof(dp)); for(int i=m-1;i>=1;i--) { for(int j=i+1;j<=m;j++) { dp[i][j] = min(dp[i+1][j] + add[s[i]-'a'],dp[i+1][j] + red[s[i]-'a']); //删除s[i]或增加s[i] dp[i][j] = min(dp[i][j],dp[i][j-1] + red[s[j]-'a']);//删除s[j] dp[i][j] = min(dp[i][j],dp[i][j-1] + add[s[j]-'a']);//增加s[j] if(s[i] == s[j]) dp[i][j] = min(dp[i][j] ,dp[i+1][j-1]); } } return dp[1][m];}int main(){ char ch[1]; while(scanf("%d%d",&n,&m)!=EOF) { scanf("%s",s+1); for(int i=1;i<=n;i++) { scanf("%s",ch); scanf("%d%d",&add[(ch[0]-'a')],&red[(ch[0]-'a')]); } int ans = Solve(); printf("%d\n",ans); } return 0;}