Description

小B的名字是由前n个小写字母组成的一个长度为m字符串。一天，小B看上了一个金发碧眼的漂亮妹子，但妹子在知道了小B的名字后，就无情地抛弃了小B，而原因竟然是小B的名字不够优美！在小B的追问下，妹子告诉小B，只有回文串是优美的。于是小B决定把自己的名字变得优美，但每加入或删除一个字母都要付出一定的代价。为了小B的人生大事，请你告诉小B他最少需要付出多少代价。

Input

第一行两个数分别表示n和m。
第二行是一个长度为m的字符串，仅由前n个小写字母组成。
接下来n行，每行含有一个字母和两个正整数，表示添加和删除这个字母的费用。

Output

一行一个整数，表示最小费用。

Hint

【数据规模与约定】
对于前30%的数据，m <= 10
对于前50%的数据，m <=100
对于前100%的数据，n<=26,m<=2000,0<=费用<=10000

Source

BY BPM

Solution

dp专题的时候见过类似题目

考虑dp。设f[i][j]表示原字符串i~j位处理完成为回文串的最小费用。分类讨论

把第i位改成j
把第j位改成i
两边同时删掉
两边相同保留
删i
删j
在i处插入j
在j处插入i

继续分析可以发现1、2操作是可以去掉的。1操作相当于7操作+5操作，2操作同理

区间dp，注意转移按照区间的大小顺序进行。

详细转移看程序吧

Code

#include <stdio.h>
#include <string.h>
#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)
#define drp(i, st, ed) for (int i = st; i >= ed; i -= 1)
#define fill(x, t) memset(x, t, sizeof(x))
#define min(x, y) (x)<(y)?(x):(y)
#define INF 0x3f3f3f3f
#define N 2001
int f[N][N], ch[N], a[N], b[N];
char str[N];
int main(void){
    freopen("ya.in", "r", stdin);
    freopen("ya.out", "w", stdout);
int n, m;
    scanf("%d%d", &n, &m);
    scanf("%s", str);
    rep(i, 1, n){
        getchar();
        scanf("%c", &ch[i]);
        scanf("%d%d", &a[ch[i]], &b[ch[i]]);
    }
    fill(f, 0);
    rep(k, 2, m){
        rep(i, 1, m - k + 1){
int j = i + k - 1;
            f[i][j] = INF;
            if (str[i - 1] == str[j - 1]){
                f[i][j] = f[i + 1][j - 1];
                continue;
            }
            f[i][j] = min(f[i][j], f[i + 1][j] + b[str[i - 1]]);
            f[i][j] = min(f[i][j], f[i + 1][j] + a[str[i - 1]]);
            f[i][j] = min(f[i][j], f[i][j - 1] + b[str[j - 1]]);
            f[i][j] = min(f[i][j], f[i][j - 1] + a[str[j - 1]]);
        }
    }
int ans = f[1][m];
    printf("%d\n", ans);
return 0;
}

秒客网

017年8月8日提高组T2 呀！回文串