poj3280(回文串，DP)

题目链接：

/*
题目大意：
    一串字符，每添加一个字符或删去一个字符都要付出相应的花费
求将这串字符变成回文串的最小花费

思路：
    删除一个字符和添加一个字符是等价的，所以考虑最小的一种即可
    d[i][j]表示区间[i,j]的最小花费
当a[i] == a[j]时， 区间[i,j]的花费就等于区间[i+1,j-1]的花费
当a[i] != a[j]时
        添加或删除a[i]，花费为d[i+1][j]+cost[ a[i]-'a' ]
        添加或删除a[j]，花费为d[i][j-1]+cost[ a[j]-'a' ]
*/
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int N = 2010; const int inf = 0x3f3f3f3f; char a[N]; int cost[30]; int d[N][N]; int main() { int n,m,i,j; while(~scanf("%d%d",&n,&m)) { scanf("%s",a); while(n--) { char c[2]; scanf("%s%d%d",c,&i,&j); cost[ c[0] - 'a' ] = min(i, j); } memset(d, 0, sizeof(d)); for(j = 0; j < m; j ++) { for(i = j-1; i >= 0; i --) { if(a[i] == a[j]) d[i][j] = d[i+1][j-1]; else d[i][j] = min(d[i+1][j] + cost[ a[i]-'a' ], d[i][j-1] + cost[ a[j]-'a' ]); } } printf("%d\n",d[0][m-1]); } return 0; }