題目鏈接：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