题目链接：http://poj.org/problem?id=3280
题目大意就是给你一个字符串，和字符串中每一个字母删除或者添加所需要付出的代价，问把它变成一个回文字串所需要的最少的代价。
首先明确一个问题，如果我们在字符串中某一个位置删除一个字符，那么一定能找到一个等价的添加的方法，所以可以把删除和添加统一到一起，然后这道题的状态就简单了。
dp[i][j]表示的是区间[i, j]内形成回文串所需要的最少的代价，这样我们就可以由一个单位字符向外扩展，状态转移方程就应该是dp[j][i] = min(dp[j + 1][i] + cost[s[j] - 'a'], dp[j][i - 1] + cost[s[i] - 'a'])，另外如果区间的首尾字符都是一样的话，那么首尾字符全都删去还是一个回文串，这样一来再把两个代价做一个比较就可以了吧。
当然，其实最初的想法是扩展出来四个状态，就是首删除，首添加，尾删除，尾添加，由此扩展开来求一个最小值，不过看了一下解题报告，再加上和学长们YY一会儿，发现了可以统一的问题，就想出来了。
view code
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5 int dp[2010][2010], x, y, cost[30];
6 char s[2010];
7 int n, m;
8 int main(){
9 while (~scanf("%d%d", &n, &m)){
10 scanf("%s", s);
11 memset(dp, 0, sizeof(dp));
12 char ss[2];
13 for (int i = 0; i < n; i++){
14 int x, y;
15 scanf("%s%d%d", ss, &x, &y);
16 cost[ss[0] - 'a'] = min(x, y);
17 }
18 for (int i = 1; i < m; i++)
19 for (int j = i - 1; j >= 0; j--){
20 dp[j][i] = min(dp[j + 1][i] + cost[s[j] - 'a'], dp[j][i - 1] + cost[s[i] - 'a']);
21 if (s[i] == s[j])
22 dp[j][i] = min(dp[j][i], dp[j + 1][i - 1]);
23 }
24 printf("%d\n", dp[0][m - 1]);
25 }
26 return 0;
27