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

题目

题目描述

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

Description

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

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

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

add 在字符串的任意位置添加一个字符
erase 删除一个字符
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

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;
}