本题没有可用的提交语言。
P2890 [USACO07OPEN] Cheapest Palindrome G
题目描述
给定一个由 n 个不同的小写字母构成的长 m 的字符串 s。可以通过在 s 的任意位置增减字母将 s 改为回文串。增减字母的花费不同,求最小花费。
输入格式
第 1 行是两个整数 n,m。
第 2 行是字符串 s。
接下 n 行,每行一个字符 c 和两个整数 x,y,表示添加一个 c 的花费为 x,删除一个 c 的花费为 y。
输出格式
只有 1 行,表示最小花费。
输入输出样例 #1
输入 #1
3 4
abcb
a 1000 1100
b 350 700
c 200 800
输出 #1
900
说明/提示
对于 100% 的数据,1≤m≤2×103,1≤n≤26,0≤x,y≤104。
by @Fish_Know_Forever