Cheapest Palindrome poj-3280
題目大意：給出一個字符串，以及每種字符的加入代價和刪除代價，求將這個字符串通過刪減元素變成回文字符串的最小代價。
poj1741， 注釋：每種字符都是小寫英文字符，1<=代價cost<=1000，字符串長度<=2000.
想法：通過之前兩道區間dp的鋪墊，對區間dp有了一個大概的了解，但是這道題無疑是一道比較特別的區間dp。
首先，我們設dp狀態，這顯然是容易的：ans[i][j]表示將原字符串從i到j變成回文串的最小代價。
之后，我們考慮轉移方程：對于一個字符串，我們顯然不可以想之前的dp一樣枚舉端點，一是回文串并不滿足兩個回文串捏一起還是回文串的性質；二是枚舉斷點的時間復雜度是$O(n^3)$的，我們并不能承受。考慮其他的轉移方式，通過回文串的性質，我們可以很清楚的明白——只有通過這個字符串的中間進行轉移才是可行的。我們想到：
分兩種情況：
1.s[i]==s[j]這時ans[i][j]=ans[i+1][j-1](此處注意，當這個字符串長度是2時，ans[i][j]=0)
2.s[i]!=s[j]，這時我們可以通過對于端點元素的增減來達到以第一種情況
ans[i][j]=min(ans[i][j],min(ans[i][j]+min(val[s[j]-'0'],del[s[j]-'0']),ans[i+1][j]+min(val[s[i]-'0'],del[s[i]-'0'])));
最后，附上丑陋的代碼... ...
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char s[2010];
int ans[2010][2010];
int val[200];
int del[220];
char a[10];
int v,d;
int main()
{int n,m;scanf("%d%d",&n,&m);scanf("%s",s+1);for(int i=1;i<=n;i++){scanf("%s%d%d",a+1,&v,&d);int middle=a[1]-'0';val[middle]=v;del[middle]=d;}memset(ans,0x3f,sizeof(ans));for(int i=1;i<=m;i++){ans[i][i]=0;}for(int len=2;len<=m;len++){for(int i=1;i<=m;i++){if(i+len-1>m) break;if(s[i]==s[i+len-1]){if(len==2) ans[i][i+len-1]=0;ans[i][i+len-1]=min(ans[i][i+len-1],ans[i+1][i+len-2]);}ans[i][i+len-1]=min(ans[i][i+len-1],min(ans[i][i+len-2]+min(val[s[i+len-1]-'0'],del[s[i+len-1]-'0']),ans[i+1][i+len-1]+min(val[s[i]-'0'],del[s[i]-'0'])));}}printf("%d\n",ans[1][m]);return 0;
}
? 小結：這個題于端點的處理是很細膩的。
在寫這個恐怖的轉移方程時注意換行，在逗號和分號都是可以換行的。
len==2時需要特判qwq
