M_sea

洛谷2890 便宜的回文Cheapest Palindrome
题目描述字串S长M,由N个小写字母构成。欲通过增删字母将其变为回文串,增删特定字母花费不同,求最小花费。传送门算法...
扫描右侧二维码阅读全文
28
2017/09

洛谷2890 便宜的回文Cheapest Palindrome

题目描述

字串S长M,由N个小写字母构成。欲通过增删字母将其变为回文串,增删特定字母花费不同,求最小花费。

传送门

算法

这是一道区间DP题,区间即字符串中的某连续字串。

设$f[i] [j]$表示字符串中i到j个字符变为回文的最小花费。
那么若$s[i]=s[j]$,花费就等于$f[i+1] [j-1]$。
否则有四种选择:

  1. 在最后插入一个s[i]字符,花费为add[s[i]]
  2. 在最前删除一个s[i]字符,花费为del[s[i]]
  3. 在最前插入一个s[j]字符,花费为add[s[j]]
  4. 在最后删除一个s[j]字符,花费为del[s[j]]

取最小值即可。

边界为$f[i] [i]=0$,不需要特殊处理;答案为$f[1] [m]$。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
char str[2010]; //输入字符串
int add[210],del[210]; //字母增加/删除花费
int f[2010][2010]; //DP数组
int main()
{
    int n,m;
    cin>>n>>m>>(str+1); //cin输入比较兼容
    for (int i=1;i<=n;i++)
    {
        char k;
        cin>>k; //输入
        cin>>add[k]>>del[k];
    }
    for (int l=2;l<=m;l++) //区间DP:长度
        for (int i=1;i+l-1<=m;i++) //左端点
        {
            int j=i+l-1; //右端点
            if (str[i]==str[j]) f[i][j]=f[i+1][j-1]; //相同
            else f[i][j]=min(f[i+1][j]+min(add[str[i]],del[str[i]]),f[i] [j-1]+min(add[str[j]],del[str[j]])); //不相同,取最小值
        }
    printf("%d\n",f[1][m]); //输出
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 15 PM

发表评论