P2890 [USACO07OPEN] Cheapest Palindrome G
题目描述
给定一个由 $n$ 个不同的小写字母构成的长 $m$ 的字符串 $s$。可以通过**在 $\bm{s}$ 的任意位置**增减字母将 $s$ 改为回文串。增减字母的花费不同，求最小花费。
输入格式
第 $1$ 行是两个整数 $n,m$。
第 $2$ 行是字符串 $s$。
接下 $n$ 行，每行一个字符 $c$ 和两个整数 $x,y$，表示添加一个 $c$ 的花费为 $x$，删除一个 $c$ 的花费为 $y$。
输出格式
只有 $1$ 行，表示最小花费。
说明/提示
对于 $100\%$ 的数据，$1\le m\le2\times10^3,1\le n\le 26,0\le x,y\le 10^4$。
$\mathrm{by\ @}$[$\mathrm{Fish\_Know\_Forever}$](/user/663215)