题意： 给出一个由m中字母组成的长度为n的串，给出m种字母添加和删除花费的代价，求让给出的串变成回文串的代价。
分析：我们知道添加最少的字母让其回文是经典的DP。可以转化为LCS来解，即枚举中间点，计算前后的最长公共子序列长度MAX,最后总长度减掉2倍MAX就可以了。那么这个题多了一个价值，我们不能这样做了，那么我们怎么做呢？

考虑这么一个区间DP。DP[i][j]代表区间i,j是回文的最小代价，那么转移很容易想到：

当s[i]==s[j]dp[i][j]=dp[i+1][j−1]

当dp[i+1][j]回文时，dp[i][j]=dp[i+1][j]+min(add[i],del[i])

当dp[i][j−1]回文时，dp[i][j]=dp[i][j−1]+min(add[j],del[j])

可以发现这个区间DP,实际上是二维的，它没有枚举断点的过程。

代码如下：

//
//Created by BLUEBUFF 2016/1/10
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b) memset(a, b, sizeof(a))
#define MP(x, y) make_pair(x,y)
template <class T1, class T2>inline void getmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void getmin(T1 &a, T2 b) { if (b<a)a = b; }
const int maxn = 210;
const int maxm = 1e5+5;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
const int rev = (mod + 1) >> 1; // FWT
//const double PI = acos(-1);
//head

int  m, n;
char s[2010];
int dp[2010][2010];
map <char, int> mp;
int main()
{
    while(scanf("%d%d", &m, &n) != EOF)
    {
        mp.clear();
        scanf("%s", s + 1);
        REP2(i, 1, m){
            char op[3];
            int x, y;
            scanf("%s%d%d", op, &x, &y);
            mp[op[0]] = min(x, y);
        }
        CLR(dp, 0);
        for(int len = 1; len <= n; len++){
            for(int i = 1; i + len - 1 <= n; i++){
                int j = i + len - 1;
                dp[i][j] = INF;
                if(s[i] == s[j]){
                    dp[i][j] = dp[i + 1][j - 1];
                }
                else{
                    dp[i][j] = min(dp[i+1][j] + mp[s[i]], dp[i][j]);
                    dp[i][j] = min(dp[i][j-1] + mp[s[j]], dp[i][j]);
                }
            }
        }
        cout << dp[1][n] << endl;
    }
    return 0;
}