【POJ 3280】 Cheapest Palindrome(动态规划 回文串)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 19 日

题意:现在有一个由n个字符组成的长度为m的字符串,可以对其通过增加字符或者删除字符来使其变成回文字符串,而增加或者删除字符都有一个花费,求解使该字符串变成回文所进行操作的最小花费.
用dp[start][end]表示使字符串ss[being]……ss[end]变成回文字符串所需的最小花费,只需考虑开始位置和结束位置即可.
1> 如果ss[begin]!=ss[end],那么有四种操作可以使其变成回文:
a> 在dp[begin+1][end]处添加或者删除字符ss[begin],所以这两种操作花费为:dp[begin][end]=min{dp[begin+1][end]+add[begin],dp[begin+1][end]+del[begin]}
用cost[begin]表示cost[begin]=min(add[begin],del[begin]),则上述方程可以写成:dp[begin][end]=dp[begin+1]+cost[begin]
b> 在dp[begin][end-1]处添加或者删除字符ss[end],所以这两种操作的花费为:dp[begin][end]=dp[begin][end-1]+cost[end]
2> 如果ss[begin]=ss[end],那么有两种情况构成回文数,即字符串保持不变和删除ss[begin]和ss[end],也就是选择dp[begin][end]与dp[begin+1][end-1]中的最小值.
综上所述:状态转移方程为:
ss[i]!=ss[j] dp[begin][end]=min{dp[begin+1][end]+cost[begin],
dp[begin][end-1]+cost[end]}
ss[i]=ss[j] dp[begin][end]=min{dp[begin][end],dp[begin+1][end-1]}

#include<iostream>  
#include<string>  
#include<algorithm>  
using namespace std;  
const int MAXM=2005;  
int dp[MAXM][MAXM];  
int cost[30];  
int main()  
{  
    freopen("1.txt","r",stdin);  
    int i,j,n,m,a,b;  
    char s;  
    string ss;  
    cin>>n>>m;  
    cin>>ss;  
    for(i=0;i<n;i++)  
    {  
        cin>>s>>a>>b;  
        cost[s-'a']=min(a,b);  
    }  
    memset(dp,0,sizeof(dp));  
    for(j=0;j<m;j++)  
        for(i=j-1;i>=0;i--)  
        {  
            dp[i][j]=min(dp[i+1][j]+cost[ss[i]-'a'],dp[i][j-1]+cost[ss[j]-'a']);  
            if(ss[i]==ss[j])  
                dp[i][j]=min(dp[i][j],dp[i+1][j-1]);  
        }  
        cout<<dp[0][m-1]<<endl;  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日