還是回文

判斷回文串很簡單，把字符串變成回文串也不難?，F在我們增加點難度，給出一串字符(全部是小寫字母)，添加或刪除一個字符，都會產生一定的花費。那么，將字符串變成回文串的最小花費是多少呢？

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]);    }}