题意：给你m个字符。当中有n种字符，每种字符都有两个值，各自是添加一个这种字符的代价。删除一个这种字符的代价，让你求将原先给出的那串字符变成回文串的最小代价。

思路：区间dp 设dp[i][j]表示从i到j区间满足条件的最优解

状态方程：

if(str[i]==str[j])dp[i][j]=dp[i+1][j-1];

else

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

代码：

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <stdlib.h>

#include <string.h>

#include <iomanip>

#define N 10005<<1

#define INF 10000000

#define LL long long

#define eps 10E-9

#define mem(a)  memset(a,0,sizeof(a))

#define mem1(a)  memset(a,-1,sizeof(a))

#define w(a)   while(a)

#define s(a)   scanf("%d",&a)

#define ss(a,b)   scanf("%d%d",&a,&b)

#define sss(a,b,c)   scanf("%d%d%d",&a,&b,&c)

#define PI acos(-1.0)

using namespace std;

int dp[2002][2002];

int val[27];

int main(){

   int n, m, a, b;

   string str;

   char c;

   w(~ss(n,m)){

    mem(dp);

   cin>>str;

   str += '0';

   for(int i=0; i<n; i++){

      cin>>c>>a>>b;

      val[c-'a'] = min(a, b);

   }

   for(int i=m-1; i>=0; i--){

    for(int j=i+1; j<m; j++){

          if(str[i] == str[j]) dp[i][j] = dp[i+1][j-1];

          else dp[i][j] = min(dp[i+1][j] + val[str[i] - 'a'], dp[i][j-1] + val[str[j] - 'a']);

        }

    }

   cout<<dp[0][m-1]<<endl;

   }

   return 0;

}