#1972. [USACO07OPEN] Cheapest Palindrome G
[USACO07OPEN] Cheapest Palindrome G
题目描述
给定一个由 个不同的小写字母构成的长 的字符串 。可以通过在 的任意位置增减字母将 改为回文串。增减字母的花费不同,求最小花费。
输入格式
第 行是两个整数 。
第 行是字符串 。
接下 行,每行一个字符 和两个整数 ,表示添加一个 的花费为 ,删除一个 的花费为 。
输出格式
只有 行,表示最小花费。
样例
3 4
abcb
a 1000 1100
b 350 700
c 200 800
900
题目来源:洛谷 P2890