M_sea

洛谷2890 便宜的回文Cheapest Palindrome
Luogu算法这是一道区间DP题,区间即字符串中的某连续字串。设$f[i] [j]$表示字符串中i到j个字符变为回...
扫描右侧二维码阅读全文
28
2017/09

洛谷2890 便宜的回文Cheapest Palindrome

Luogu

算法

这是一道区间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 月 30 日 09 : 19 PM

发表评论