NYOJ 1023 还是回文(DP,花最少费用形成回文串)

/*
   题意：给出一串字符(全部是小写字母)，添加或删除一个字符，都会产生一定的花费。
   那么，将字符串变成回文串的最小花费是多少呢？ 

   思路：如果一个字符串增加一个字符 x可以形成一个回文串，那么从这个字符串中删除这个字符 x
         同样也能形成回文串！
         所以我们只记录删除，和增加这个字符 x 的最小的费用就好了！->转变成添加多少个字符形成回文串费用最少！ 

         str[i]!=str[k]
         dp[i][j]=min(dp[i][j-1]+cost[str[k]-'a'], dp[i+1][j-1]+cost[str[i]-'a']) ;

         str[i]==str[k]
         dp[i][j]=dp[i+1][j-2];

*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 2005
using namespace std;

int dp[N][N];

int cost[30]; 

char str[N]; 

int main(){
    int m, n;
    while(scanf("%d%d", &m, &n)!=EOF){
        scanf("%s", str+1);
        memset(cost, 0, sizeof(cost));
        while(m--){
           char ch;
           int a, b;
           getchar();
           scanf("%c %d %d", &ch, &a, &b);
           cost[ch-'a']=min(a, b);
        }
        for(int i=1; i<=n; ++i)
           dp[i][1]=0;
        for(int j=2; j<=n; ++j)
           for(int i=1; i+j-1<=n; ++i){
               int k=i+j-1;
               if(str[i]!=str[k])
                  dp[i][j]=min(dp[i][j-1]+cost[str[k]-'a'], dp[i+1][j-1]+cost[str[i]-'a']) ;
               else dp[i][j]=dp[i+1][j-2];
           }   

        printf("%d\n", dp[1][n]);
    }
    return 0;
}