poj（3280）Cheapest Palindrome（区间dp）-蒲公英云

poj（3280）Cheapest Palindrome（区间dp）

题目链接：http://poj.org/problem?id=3280

题意：给出一个由m中字母组成的长度为n的串，给出m种字母添加和删除花费的代价，求让给出的串变成回文串的代价。

分析：我们知道求添加最少的字母让其回文是经典dp问题，转化成LCS求解。这个是一个很明显的区间dp

我们定义dp [ i ] [ j ] 为区间 i 到 j 变成回文的最小代价。

那么对于dp【i】【j】有三种情况

首先：对于一个串如果s【i】==s【j】，那么dp【i】【j】=dp【i+1】【j-1】

其次：如果dp【i+1】【j】是回文串，那么dp【i】【j】=dp【i+1】【j】+min（add【i】，del【i】）；

最后，如果dp【i】【j-1】是回文串，那么dp【i】【j】=dp【i】【j-1】 + min（add【j】，del【j】）；

代码：

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 200;
const int M = 2500;
int add[N];
int dp[M][M];
int main()
{
    int n,m;
    string s;
    while(~scanf("%d%d",&n,&m))
    {
        cin>>s;
        char c;int x,y;
        for(int i=0;i<n;i++)
        {
            cin>>c>>x>>y;
            add[c]=min(x,y);
        }
        memset(dp,0,sizeof(dp));
        for(int k=1;k<s.size();k++)
        {
            for(int i=0,j=k;j<s.size();i++,j++)
            {
                dp[i][j]=0x3f3f3f3f;
                if(s[i]==s[j])
                    dp[i][j]=dp[i+1][j-1];
                else
                {
                    dp[i][j]=min(dp[i+1][j] + add[s[i]],dp[i][j]);
                    dp[i][j]=min(dp[i][j-1] + add[s[j]],dp[i][j]);
                }
            }
        }
        printf("%d\n",dp[0][s.size()-1]);
    }
    return 0;
}