题目链接：http://poj.org/problem?id=3280
题目大意：给定一个字符串，可以删除增加，每个操作都有代价，求出将字符串转换成回文串的最小代价
Sample Input
3 4
abcb
a 1000 1100
b 350 700
c 200 800
Sample Output
900
分析：这是一道最长回文串的变形，就是LCS
一串字符要变成回文，对于一个字符来说，删掉它，或者增加对称的一个该字符，都能达到回文的效果，所以是等价的。所以取代价的的时候选择最小的就可以。
至于动态规划方程：令dp[i][j]表示从第 i 个字符到第j个字符变成回文的最小代价，初始为0。接着LCS
dp[i][j] = min(dp[i+1][j]+cost[s[i]-'a'] , dp[i][j-1]+cost[s[j]-'a']) ;
if(s[i]==s[j]) dp[i][j] = min(dp[i+1][j-1],dp[i][j]);
代码如下：
# include<stdio.h>
# include<string.h>
# define maxn
char s[maxn];
int dp[maxn][maxn],cost[maxn]; int min(int a,int b){
return a<b ? a :b;
} int main(){
int n,m,a,b,i,j;
char temp;
while(scanf("%d%d",&n,&m)!=EOF){
memset(dp,,sizeof(dp));
getchar();
scanf("%s",s+);
getchar();
for(i=;i<=n;i++){
scanf("%c %d%d",&temp,&a,&b);
getchar();
cost[temp-'a'] = min(a,b);
}
for(j=;j<=m;j++){
for(i=j+;i>=;i--){
dp[i][j] = min(dp[i+][j]+cost[s[i]-'a'] , dp[i][j-]+cost[s[j]-'a']) ;
if(s[i]==s[j])
dp[i][j] = min(dp[i+][j-],dp[i][j]);
}
}
printf("%d\n",dp[][m]);
}
return ;
}