11066: 【原1066】小M家的牛们

题目

题目描述

author: wcy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1066

Description

小M是一位远近闻名的庄园主。因为近来牛肉涨价，精明小M决定开始养牛。为了方便跟踪所有的牛，小M在庄园上装了一套自动系统。他给了每一个头牛一个电子牌号。当牛走过这个系统时，牛的名字将被自动读入。

每一头牛的电子名字是一个长度为M的，由N个不同小写字母构成的字符串。

很快，淘气的牛找到了系统的漏洞：它们可以倒着走过读码器。一头名字为abcba不会导致任何问题，但是名为abcb的牛会变成两头牛（abcb和bcba）。

于是乎小M决定给牛们改名字，使得牛的名字正读和反读都一样。小M可以在任意位置添加或删除字母。但是，添加和删除每一个字母都有一定的费用。对于一个牛的名字和所有添加或删除字母的费用，找出修改名字的最小的费用。注意：空字符串也是一个合法的名字。

Input Format

第一行：两个用空格分开的数，N和M。

第二行：M个字符，初始的牛的名字。

第3到N＋2行：每行含有一个字母和两个整数，分别是添加和删除这个字母的费用。

\( 0 \leq N \leq 26，0 \leq M \leq 2000 \) ， \( 0 \leq 费用 \leq 10000 \)

Output Format

一个整数，改变所有名字的最小费用。

Sample Input

3 4
abcb
a 1000 1100
b 350 700
c 200 800

Sample Output

FineArtz's solution

/* 小M家的牛们 */
#include <iostream>
#include <cstring>
using namespace std;

int f[2005][2005] = {0};

int main(){
    int n, m;
    cin >> n >> m;
    char s[2005];
    cin >> s;
    int add[26], del[26];
    for (int i = 1; i <= n; ++i){
        char ch;
        int x, y;
        cin >> ch >> x >> y;
        add[ch - 'a'] = x;
        del[ch - 'a'] = y;
    }
    for (int i = m - 2; i >= 0; --i){
        for (int j = i; j < m; ++j){
            if (s[i] == s[j])
                f[i][j] = f[i + 1][j - 1];
            else{
                int t = 200000000;
                t = min(f[i + 1][j] + add[s[i] - 'a'], t);
                t = min(f[i + 1][j] + del[s[i] - 'a'], t);
                t = min(f[i][j - 1] + add[s[j] - 'a'], t);
                t = min(f[i][j - 1] + del[s[j] - 'a'], t);
                f[i][j] = t;
            }
        }
    }
    cout << f[0][m - 1] << endl;
    return 0;
}

yyong119's solution

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int clist[26], state[2005][2005];
string ori_name;
int N, M;

int CalCost(int l, int r) {
    int i, tem_cost1, tem_cost2, left, right;

    if (l >= r) return 0;
    if (ori_name[l] == ori_name[r]) return CalCost(++l,--r);
    if (state[l][r] >= 0) return state[l][r];
    left = ori_name[l] - 'a';
    right = ori_name[r] - 'a';
    tem_cost1 = clist[left] + CalCost(l + 1, r);
    tem_cost2 = clist[right] + CalCost(l, r - 1);
    int min_cost = tem_cost1 < tem_cost2 ? tem_cost1 : tem_cost2;
    state[l][r] = min_cost;
    return min_cost;
}

int main(){

    cin >> N >> M >> ori_name;
    for (int i = 0; i < M; ++i)
        for (int j = 0; j < M; ++j) state[i][j] = -1;

    for (int i = 0; i < N; ++i) {
        int acost, dcost;
        char cha;
        cin >> cha >> acost >> dcost;
        clist[cha - 'a'] = acost < dcost ? acost : dcost;
    }
    int min_cost = CalCost(0, M - 1);
    cout << min_cost;

    return 0;
}