题目连接：http://poj.org/problem?id=3280
题意：给定一个长度为m(m<=2000)的小写字母字符串，在给定组成该字符串的n(n<=26)个字符的添加和删除费用，求使原字符串变为回文串的最小费用。
分析：首先明确，删除一个字母和增加一个字母是等价的，如果删除一个字符一个字符使得原字符串变成回文，那么必定可以增加一个字符使原字符串变成回文，因此对于删除和增加操作去费用最少的即可。
dp[i][j]表示区间i~j形成回文串最少费用，则：
dp[i][j] = min(dp[i+1][j]+cost[str[i]-'a'], dp[i][j-1]+cost[str[j]-'a']);
if(str[i] == str[j])dp[i][j] = min(dp[i][j],dp[i+1][j-1]);
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-9
#define N 100010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int cost[],dp[][];
char s[],str[];
int dfs(int l,int r)
{
if(dp[l][r]!=-)return dp[l][r];
if(l>=r)return ;
int temp=inf;
if(str[l]==str[r])
temp=min(temp,dfs(l+,r-));
temp=min(temp,dfs(l+,r)+cost[str[l]-'a']);
temp=min(temp,dfs(l,r-)+cost[str[r]-'a']);
return dp[l][r]=temp;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)>)
{
scanf("%s",str+);
for(int i=;i<=n;i++)
{
int add,det;
scanf("%s%d%d",s,&add,&det);
cost[s[]-'a']=min(add,det);
}
FILL(dp,-);
printf("%d\n",dfs(,m)); }
}