Cheapest Palindrome- 最小代价构造回文 动态规划

题目大意 ：

给定一个长度为M(<=2000)字符串（小写字母），要求删除或添加一些字母，使得该字符串成为回文。

每种字母删除或添加的代价都是不同的。要求输出最小的代价。

 

动态规划可以解决。

令f[i][j]表示原字符串从i到j已经通过某种方式处理成为回文的最小代价。

初始f[i][i]=0;

转移方程 f[i][j]=min{ f[i+1][j]+add[i] ; f[i+1][j]+del[i] ;  f[i][j-1]+add[j] ; f[i][j-1]+del[j] ; f[i+1][j-1](if a[i]==a[j])  }

错了好几次 原因是程序中定义的“无穷大”太小>_<

源代码：

/*H - Cheapest Palindrome*/

#include <stdio.h>#define M 2002#define N 30

int f[M][M]={0};    int main(){    int i,j,k,m,n,s,t;    char a[M],st[N];    int del[N]={0},ins[N]={0};

    //input    scanf("%d%d",&n,&m);    scanf("%s",a);    for(i=0;i<n;i++)    {        scanf("%s",st);        scanf("%d%d",&ins[st[0]-'a'],&del[st[0]-'a']);    }        //DP    for(k=1;k<m;k++)    {        for(i=0;i<m-k;i++)        {            j=i+k;            s=99999999;    /***/            if(a[i]==a[j] && f[i+1][j-1] < s) s=f[i+1][j-1];            if(f[i+1][j]+del[a[i]-'a'] < s) s=f[i+1][j]+del[a[i]-'a'];            if(f[i][j-1]+del[a[j]-'a'] < s) s=f[i][j-1]+del[a[j]-'a'];            if(f[i+1][j]+ins[a[i]-'a'] < s) s=f[i+1][j]+ins[a[i]-'a'];            if(f[i][j-1]+ins[a[j]-'a'] < s) s=f[i][j-1]+ins[a[j]-'a'];            //printf("k=%d: [%d - %d] = %d/n",k,i,j,s);            f[i][j]=s;        }    }

    printf("%d/n",f[0][m-1]);    return 0;}