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

### 题目描述

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

## Input Format

$$0 \leq N \leq 26，0 \leq M \leq 2000$$ ， $$0 \leq 费用 \leq 10000$$

## Sample Input

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


## Sample Output

900


## 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;
for (int i = 1; i <= n; ++i){
char ch;
int x, y;
cin >> ch >> x >> y;
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;
}