題目鏈接：http://poj.org/problem?id=3280
題目大意就是給你一個(gè)字符串，和字符串中每一個(gè)字母刪除或者添加所需要付出的代價(jià)，問把它變成一個(gè)回文字串所需要的最少的代價(jià)。
首先明確一個(gè)問題，如果我們?cè)谧址心骋粋€(gè)位置刪除一個(gè)字符，那么一定能找到一個(gè)等價(jià)的添加的方法，所以可以把刪除和添加統(tǒng)一到一起，然后這道題的狀態(tài)就簡(jiǎn)單了。
dp[i][j]表示的是區(qū)間[i, j]內(nèi)形成回文串所需要的最少的代價(jià)，這樣我們就可以由一個(gè)單位字符向外擴(kuò)展，狀態(tài)轉(zhuǎn)移方程就應(yīng)該是dp[j][i] = min(dp[j + 1][i] + cost[s[j] - 'a'], dp[j][i - 1] + cost[s[i] - 'a'])，另外如果區(qū)間的首尾字符都是一樣的話，那么首尾字符全都刪去還是一個(gè)回文串，這樣一來再把兩個(gè)代價(jià)做一個(gè)比較就可以了吧。
當(dāng)然，其實(shí)最初的想法是擴(kuò)展出來四個(gè)狀態(tài)，就是首刪除，首添加，尾刪除，尾添加，由此擴(kuò)展開來求一個(gè)最小值，不過看了一下解題報(bào)告，再加上和學(xué)長(zhǎng)們YY一會(huì)兒，發(fā)現(xiàn)了可以統(tǒng)一的問題，就想出來了。
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