1 /* 2    题意：给出一串字符(全部是小写字母)，添加或删除一个字符，都会产生一定的花费。 3    那么，将字符串变成回文串的最小花费是多少呢？  4     5    思路：如果一个字符串增加一个字符 x可以形成一个回文串，那么从这个字符串中删除这个字符 x 6          同样也能形成回文串！ 7          所以我们只记录删除，和增加这个字符 x 的最小的费用就好了！->转变成添加多少个字符形成回文串费用最少！  8           9          str[i]!=str[k] 10          dp[i][j]=min(dp[i][j-1]+cost[str[k]-‘a‘], dp[i+1][j-1]+cost[str[i]-‘a‘]) ;11          12          str[i]==str[k]13          dp[i][j]=dp[i+1][j-2];14          15 */16 #include<iostream>17 #include<cstring>18 #include<cstdio>19 #include<algorithm>20 #define N 2005 21 using namespace std;22 23 int dp[N][N];24 25 int cost[30]; 26 27 char str[N]; 28 29 int main(){30     int m, n;31     while(scanf("%d%d", &m, &n)!=EOF){32         scanf("%s", str+1);33         memset(cost, 0, sizeof(cost)); 34         while(m--){35            char ch;36            int a, b;37            getchar();38            scanf("%c %d %d", &ch, &a, &b);39            cost[ch-‘a‘]=min(a, b);40         }41         for(int i=1; i<=n; ++i)42            dp[i][1]=0;43         for(int j=2; j<=n; ++j)44            for(int i=1; i+j-1<=n; ++i){45                int k=i+j-1;46                if(str[i]!=str[k])47                   dp[i][j]=min(dp[i][j-1]+cost[str[k]-‘a‘], dp[i+1][j-1]+cost[str[i]-‘a‘]) ;48                else dp[i][j]=dp[i+1][j-2]; 49            }   50            51         printf("%d\n", dp[1][n]);52     } 53     return 0;54 }