首页 > 其他 > 详细

[区间dp] poj 3280 Cheapest Palindrome

时间:2015-05-07 16:53:39      阅读:117      评论:0      收藏:0      [点我收藏+]

题意:

给出增加或减少某个字符的代价。

给你一个串,求让它变成回文串的最小代价。

思路:

和求次数一样。

然后注意的是其实增加和减少的性质是一样的。所以对于每个字符,取修改代价最小的就行了。

意思就是取增加和减少的最小值。

其他就同求次数的区间dp了。

代码:

#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
#include"map"
using namespace std;
#define N 2010
int dp[N][N],n;
char a[N];
int va[999];
int main()
{
    int n,k;
    while(scanf("%d%d",&n,&k)!=-1)
    {
        scanf("%s",a);
        for(int i=0;i<n;i++)
        {
            char x[3];
            scanf("%s",x);
            int y,z;
            scanf("%d%d",&y,&z);
            va[x[0]-0]=min(y,z);
        }
        memset(dp,0,sizeof(dp));
        int i,j;
        for(i=k-2;i>=0;i--)
        {
            for(j=i+1;j<k;j++)
            {
                if(a[i]==a[j])
                    dp[i][j]=dp[i+1][j-1];
                else
                    dp[i][j]=min(dp[i+1][j]+va[a[i]-0],dp[i][j-1]+va[a[j]-0]);
            }
        }
        printf("%d\n",dp[0][k-1]);
    }
    return 0;
}


[区间dp] poj 3280 Cheapest Palindrome

原文:http://blog.csdn.net/wdcjdtc/article/details/45560583

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!