#P2855. USACO（110）动态规划（区间型）2：修改回文P2890 [USACO07OPEN] Cheapest Palindrome
USACO（110）动态规划（区间型）2：修改回文P2890 [USACO07OPEN] Cheapest Palindrome
Description
# [USACO07OPEN] Cheapest Palindrome G题面翻译
题目描述
跟踪所有的牛可能是一项棘手的任务，因此FJ安装了一个系统来自动化这一过程。他在每头牛身上安装了一个电子身份证标签，系统会在牛经过扫描仪时读取该标签。每个身份证标签的内容目前是一个长度为 ( M )（( 1 \leq M \leq 2000 )）的字符串，由 ( N )（( 1 \leq N \leq 26 )）个不同符号（即小写罗马字母）组成。
牛是一种顽皮的生物，有时会试图通过倒退行走来欺骗系统。虽然ID为“abcba”的牛无论朝哪个方向走都能读取相同的值，但ID为“abcb”的牛可能会注册为两个不同的ID（“abcb”和“bcba”）。
FJ希望更改牛的ID标签，使其无论牛朝哪个方向走都能读取相同的值。例如，可以通过在末尾添加“a”来将“abcb”更改为“abcba”，使其成为回文（正着和反着读都相同）。将ID更改为回文的其他方法包括在开头添加三个字母“bcb”以形成ID“bcbabcb”或删除字母“a”以形成ID“bcb”。可以在字符串的任何位置添加或删除字符，从而生成比原始字符串更长或更短的字符串。
不幸的是，由于ID标签是电子的，每次插入或删除字符都有一个成本（( 0 \leq \text{cost} \leq 10,000 )），该成本取决于要添加或删除的确切字符值。给定牛的ID标签的内容以及插入或删除每个字母的成本，找出更改ID标签以满足FJ要求的最低成本。空的ID标签被视为满足正向和反向读取相同的要求。只有具有相关成本的字母可以添加到字符串中。
输入格式
第一行：两个以空格分隔的整数：( N ) 和 ( M )
第二行：该行包含恰好 ( M ) 个字符，构成初始ID字符串
第三到 ( N+2 ) 行：每行包含三个以空格分隔的实体：输入字母表的一个字符和两个整数，分别是添加和删除该字符的成本。
输出格式
第一行：一行包含一个整数，即更改给定名牌的最低成本。
样例 #1
样例输入 #1
3 4
abcb
a 1000 1100
b 350 700
c 200 800
样例输出 #1
900
提示
变成 bcbabcb 的代价为 350+200+350 = 900
</p>Hint
by hansang:#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
typedef long long LL;
char s[N]; LL f[N][N];
struct node{LL x, y, mn;} a[N];
int main(){
int n, m; scanf("%d%d", &m, &n);
scanf("%s", s+1);
for(int i=1; i<=m; i++){
char ss[5]; scanf("%s", ss);
int t=ss[0]-'a';
scanf("%lld%lld", &a[t].x, &a[t].y);
a[t].mn=min(a[t].x, a[t].y);
}
memset(f, 0x3f, sizeof(f));
for(int i=n; i>=1; i--){
f[i][i]=0;
for(int j=i+1; j<=n; j++){
int t1=s[i]-'a', t2=s[j]-'a';
f[i][j]=min(f[i+1][j]+a[t1].mn, f[i][j-1]+a[t2].mn);
if(s[i]==s[j]){
if(i+1==j) f[i][j]=0;
else f[i][j]=min(f[i][j], f[i+1][j-1]);
}
}
}
printf("%lld\n", f[1][n]);
return 0;
}