【poj 3280】Cheapest Palindrome題意＆題解＆コード(C＋＋)

タイトルリンク:http://poj.org/problem?id=3280 題意:あるアルファベット(追加または削除)を修正する価値を与え、最小化してエコー文字列にする価値を求める文字列を与えます.題解:最長回文サブシーケンスを求める変形のような気がしますが、最初は最長回文サブシーケンスを求めるような方法で文字列を反転させて元の文字列と最長共通サブシーケンスをマッチングさせ、マッチングの過程でdp転送をしようと考えていましたが、それがダメであることに気づき、ネット上の方法を参考にしてdp[i][j]を使いました処理済み区間がi～j間の文字列を回文文字列に変える最小の代価を表すと,遷移方程式が明らかになる.

    if (s[i-1]==s[j-1])
    dp[i][j]=dp[i+1][j-1];
    else
    dp[i][j]=min(dp[i+1][j]+cost[ci],dp[i][j-1]+cost[cj]);

もう一つ、削除と修正は2つの費用ですが、実際には修正するたびに追加と削除の効果は同じなので、毎回必ず最小の費用を取り、新しい配列を開いて保存すると毎回比較する必要はありません.
コード:

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
int n,m,cost[2005],dp[2005][2005];
char s[2005];
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s",s);
    for (int i=1;i<=n;i++)
    {
        char c[2];
        int a1,a2;
        scanf("%s%d%d",c,&a1,&a2);
        cost[c[0]-'a']=min(a1,a2);
    }
    //for (int i=1;i<=m;i++)
    //for (int j=1;j<=m;j++)
    //dp[i][j]=1e9+7;
    //for (int i=1;i<=m;i++)
    //dp[i][i]=0;
    //       dp   ，     (i,j)(i<j)        
    for (int i=m;i>=1;i--)
    for (int j=i+1;j<=m;j++)
    if (s[i-1]==s[j-1])
    //  j=i+1     i+1>j-1          ，    。
    dp[i][j]=dp[i+1][j-1];
    else
    {
        int ci=s[i-1]-'a';
        int cj=s[j-1]-'a';
        dp[i][j]=min(dp[i+1][j]+cost[ci],dp[i][j-1]+cost[cj]);
    }
    printf("%d
",dp[1][m]);
}