Skip to content

11071: 【原1071】小M的回文串

题目

题目描述

author: 寿鹤鸣 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1071

Description

小M喜欢回文串,回文串就是从左往右和从右往左读都一样的字符串。

现在小X找到小M给了他一个字符串S,希望小M将它变成回文串。

小M可以进行如下三类操作:

  1. add 在字符串的任意位置添加一个字符
  2. erase 删除一个字符
  3. change one letter to another 将某个字符变成另一个

然而,每种操作只能对规定的字符有效。如,小M只能允许erase 'a', add 'b', change 'c' to 'd',且没有其他操作可以使用。 世界上没有免费的午餐,小M的每次操作都有一定的花费。

Input Format

第一行一个字符串,表示小M需要修改的字符串 (\( length \leq 50 \))

第二行一个数N, 表示小M可以使用的操作 (\( N \leq 50 \) )

接下来N行,每行一个可以使用的操作,有下面三种形式:

"add c x" : 表示将一个字符c加入到串中需要的花费为x

"erase c x" : 表示将一个字符c从串中删除需要的花费为x

"change c1 c2 x" : 表示将某个字符c1变为c2需要的花费为x

注意,"change c1 c2 x" 不允许将c2变成c1

满足 \( x \leq 100000, c1 <> c2 \) , 且任两行操作不同

Output Format

一行一个数,表示小M将初始的字符串转为回文串的最小花费,如果不可能,输出-1

Sample Input

caaaaaab
6
change b a 100000
change c a 100000
change c d 50000
change b e 50000
erase d 50000
erase e 49999

Sample Output

199999

FineArtz's solution

/* 小M的回文串 */
#include <iostream>
#include <cstring>
using namespace std;

const long long INF = 100000000000000LL;

int main(){
    char s[51];
    cin >> s;
    int n, m = strlen(s);
    cin >> n;
    long long a[256], e[256], c[256][256];
    long long cost[256];
    for (int i = 0; i < 256; ++i){
        a[i] = INF;
        e[i] = INF;
        cost[i] = INF;
        for (int j = 0; j < 256; ++j){
            if (i == j)
                c[i][j] = 0;
            else
                c[i][j] = INF;
        }
    }
    for (int i = 1; i <= n; ++i){
        char t[10];
        char x, y;
        int w;
        cin >> t;
        switch(t[0]){
        case 'a':
            cin >> x >> w;
            a[x] = w;
            break;
        case 'e':
            cin >> x >> w;
            e[x] = w;
            break;
        case 'c':
            cin >> x >> y >> w;
            c[x][y] = w;
            break;
        }
    }
    for (int k = 0; k < 256; ++k){
        for (int i = 0; i < 256; ++i){
            for (int j = 0; j < 256; ++j){
                if (i != j && i != k && j != k)
                    if (c[i][j] > c[i][k] + c[k][j])
                        c[i][j] = c[i][k] + c[k][j];
            }
        }
    }
    for (int i = 0; i < 256; ++i){
        for (int j = 0; j < 256; ++j){
            cost[i] = min(cost[i], min(a[i], e[i]));
            cost[i] = min(cost[i], c[i][j] + min(a[j], e[j]));
            cost[i] = min(cost[i], a[j] + c[j][i]);
            for (int k = 0; k < 256; ++k)
                cost[i] = min(cost[i], c[i][j] + a[k] + c[k][j]);
        }
    }
    long long f[51][51] = {0};
    for (int i = m - 2; i >= 0; --i){
        for (int j = i + 1; j < m; ++j){
            if (s[i] == s[j])
                f[i][j] = f[i + 1][j - 1];
            else{
                f[i][j] = INF;
                f[i][j] = min(f[i][j], f[i + 1][j] + cost[s[i]]);
                f[i][j] = min(f[i][j], f[i][j - 1] + cost[s[j]]);
                f[i][j] = min(f[i][j], f[i + 1][j - 1] + min(c[s[j]][s[i]], c[s[i]][s[j]]));
                for (int k = 0; k < 256; ++k)
                    f[i][j] = min(f[i][j], f[i + 1][j - 1] + c[s[i]][k] + c[s[j]][k]);
            }
        }
    }
    if (f[0][m - 1] == INF)
        cout << "-1" << endl;
    else
        cout << f[0][m - 1] << endl;
    return 0;
}