POJ3280 Cheapest Palindrome

タイトルリンク:http://poj.org/problem?id=3280
タイトルの大意はあなたに1つの文字列をあげて、文字列の中のすべてのアルファベットが削除してあるいは必要な代価を追加して、それを1つの文字列に戻すのに必要な最小限の代価を聞きます.
まず、文字列のいずれかの位置で文字を削除すると、等価な追加方法が必ず見つかるので、削除と追加を統一することができ、この問題の状態が簡単になります.
dp[i][j]は区間[i,j]内でエコー列を形成するのに必要な最小限の代価を表し、これにより1つの単位文字から外に拡張することができ、状態遷移方程式はdp[j][i]=min(dp[j+1][i]+cost[s[j]-'a',dp[j][i-1]+cost[s[i]-'a')であるべきであり、また区間の先頭文字が同じであれば、では、最初と最後の文字はすべて削除しても1つの文字列で、これで2つの代価を1つ比較すればいいのではないでしょうか.
もちろん、最初の考えは4つの状態を拡張することで、首削除、首追加、尾削除、尾追加ということで、拡張して最小値を求めるのですが、問題解決報告書を見て、先輩たちとYYを加えてしばらくして、統一できる問題を見つけて、思いつきました.

#include 
#include 
#include 
using namespace std;
int dp[2010][2010], x, y, cost[30];
char s[2010];
int n, m;
int main(){
    while (~scanf("%d%d", &n, &m)){
        scanf("%s", s);
        memset(dp, 0, sizeof(dp));
        char ss[2];
        for (int i = 0; i < n; i++){
            int x, y;
            scanf("%s%d%d", ss, &x, &y);
            cost[ss[0] - 'a'] = min(x, y);
        }
        for (int i = 1; i < m; i++)
          for (int j = i - 1; j >= 0; j--){
              dp[j][i] = min(dp[j + 1][i] + cost[s[j] - 'a'], dp[j][i - 1] + cost[s[i] - 'a']);
              if (s[i] == s[j])
                dp[j][i] = min(dp[j][i], dp[j + 1][i - 1]);
          }
        printf("%d
", dp[0][m - 1]);
    }
    return 0;
}