题解 P2890 【[USACO07OPEN]便宜的回文Cheapest Palindrome】

zhenglier · 2019-07-09 15:19:27 · 题解

更好的阅读体验

区间DP

设f[i][j]为从i到j这段区间被修正为回文串的最小花费，c[ch][0]为添加字符ch的花费，c[ch][1]为删去字符ch的花费，s为题目给出的串。为可以用如下几个转移：

用[i+1,j]区间转移：这种转移相当于在[i+1,j]区间的左边加入一个字符，让[i,j]变为回文的方法为在左边删去该字符或在右边加上该字符，有转移方程：

f[i][j]=min(f[i][j],f[i+1][j]+min(c[s[i]][0],c[s[i]][1]))

用[i,j-1]区间转移：这种转移相当于在[i,j-1]区间的右边加入一个字符，方法同上：

f[i][j]=min(f[i][j],f[i][j-1]+min(c[s[j]][0],c[s[j]][1]))

当前区间[i,j]满足s[i]==s[j]，直接用[i+1,j-1]转移:

f[i][j]=min(f[i][j],f[i+1][j-1])

然后就可以愉快地写代码了：

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int n,m;
char s[N];
int c[255][2];
int f[N][N];
int main(){
    cin>>m>>n;
    scanf("%s",s+1);
    for(int i=1;i<=m;++i){
        char op[2];
        int a,b;
        scanf("%s %d %d",op,&a,&b);
        c[op[0]][0]=a;
        c[op[0]][1]=b;
    }
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;++i)f[i][i]=0;
    for(int i=0;i<=n+1;++i){
        for(int j=0;j<i;++j)f[i][j]=0;
    }
    for(int k=1;k<=n;++k){
        for(int i=1;k+i<=n;++i){
            int j=k+i;
            f[i][j]=min(f[i+1][j]+min(c[s[i]][0],c[s[i]][1]),
                        f[i][j-1]+min(c[s[j]][0],c[s[j]][1]));
            if(s[i]==s[j]){
                if(j-i==1)f[i][j]=0;
                else f[i][j]=min(f[i][j],f[i+1][j-1]);
            }
        }
    }
    cout<<f[1][n]<<endl;
}