还是回文

还是回文

判断回文串很简单，把字符串变成回文串也不难。现在我们增加点难度，给出一串字符(全部是小写字母)，添加或删除一个字符，都会产生一定的花费。那么，将字符串变成回文串的最小花费是多少呢？

3 4abcba 1000 1100b 350 700c 200 800样例输出
900
回文串，给你一个字符串，通过添加或则删除其中的一些字符，变为回文字符串，但是添加或则删除一个字符的代价不同
让求最小的代价
假设dp[i][j]表示从i个字符到j个字符构成回文发费的最小代价
那么存在：dp[i][j] = Min(dp[i+1][j]+cost[i],dp[i]j-1]+cost[j])其中cost[i]为添加i或则号字符的最小代价
如果str[i] == str[j]  dp[i][j] = Min(dp[i-1][j+1],dp[i][j])
可以看出2状态时依托1状态的
例如样例（abcb）：
dp[0][1]=MIN( dp[1][1] + (cost[0]=1000)  ,dp[0][0] + ( cost[1] + 350 ) ) = 350;所求的过程是求操作a或b看哪个的费用少，当是abc, 第一步先操作b和c，求出最小的费用dp[1][2] = 200; 第二步操作ab和c  或 a和bc ，因为ab和bc 的回文串已经求出，所以ab和bc看成一个整体，求abc回文字符串的最小费用为dp[0][2]=550;  当为abcb时，第一步求c和b为dp[2][3]=200;第二步求b和cb或bc和b,和之前的一样，因为str[1] == str[3] ，bcb已经为回文串，所以更新dp[1][3]的值为0，下一步求dp[0][3]=900;
#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>using namespace std;struct node{    int tian,shan;}a[3000];int dp[3000][3000];int zhi[100];int main(){    int n,m;    char s[3000];    while(scanf("%d%d",&n,&m)!=-1)    {        scanf("%s",s);        memset(dp,0,sizeof(dp));        char w[10];        for(int i=0;i<n;i++)        {            scanf("%s",w);            scanf("%d %d",&a[i].tian,&a[i].shan);            zhi[w[0]-'a']=min(a[i].tian,a[i].shan);        }        for(int i=1;i<m;i++)        {            for(int j=i-1;j>=0;j--)            {                dp[j][i]=min(dp[j+1][i]+zhi[s[j]-'a'],dp[j][i-1]+zhi[s[i]-'a']);                if(s[i]==s[j])                {                    dp[j][i]=min(dp[j+1][i-1],dp[j][i]);                }            }        }        PRintf("%d/n",dp[0][m-1]);    }}