题目大意：
给一个字符串
可以再任意位置添加或删除字母（给出花费的） 使得字符串变成回文
做法：
其实添加和删除的性质是一样的
添加一个字母和删去相对应的字母 对于使原文变成回文
的贡献是一样的 所以我们取花费的时候 只取小的花费
为了理解方面统一用删除吧
从两端进行遍历
1 如果对应相等 则直接去掉就可以 （无需花费）
2 如果只有一个字符了 直接去掉 （无需花费）
3 否则选择删掉左边 和 删掉右边 两种情况中最优的（只有给出花费才能删）出花费的） 使得字符串变成回文
注意：
用一个数组标记，目的是为了记忆这个状态曾经的结果。
代码：
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<stdlib.h>
#define INF_MAX 0x7fffffff
#define INF 999999
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{int u;int v;int w;bool friend operator < (node a, node b){return a.w < b.w;}
}edge[1001];
int gcd(int n,int m){if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);}
int lcm(int n,int m){if(n<m) swap(n,m);return n/gcd(n,m)*m;}
int v[27];
char str[10001];
int as[2001][2001];
int dos(int l,int r)
{if(l>r)return 0;if(as[l][r]!=-1)return as[l][r];//记忆化搜索if(l==r){as[l][r]=0;return 0;}else if(str[l]==str[r]){as[l][r]=dos(l+1,r-1);return as[l][r];}else{as[l][r]=min(dos(l+1,r)+v[str[l]-'a'],dos(l,r-1)+v[str[r]-'a']);return as[l][r];}
}
int main()
{int n,m,i,a,b;char c;scanf("%d%d%*c",&n,&m);gets(str);mem(as,-1);for(i=0;i<n;i++){scanf("%c%d%d%*c",&c,&a,&b);v[c-'a']=min(a,b);}as[0][m-1]=dos(0,m-1);printf("%d\n",as[0][m-1]);return 0;
}