登录/注册
308. 最廉价的回文串 Cheapest Palindrome(挑战程序设计竞赛)
时间限制: C/C++ 1000 ms | 其他语言 2000 ms
内存限制: C/C++ 64 MB | 其他语言 128 MB
尝试次数: 37 | 通过次数: 15
尝试人数: 5 | 通过人数: 5
标签: 动态规划
难度: 中等
0
0

给定一个长度为 m(m2000)m(m \leq 2000) 的小写字母字符串, 在给定组成该字符串的 n(n26)n(n \leq 26) 个字符的添加和删除费用, 求使原字符串变为回文串的最小费用。

输入

  • 第一行包含两个整数 nnmm
  • 第二行为长度为 mm 的字符串, 接下来有 nn 行, 每行首先是一个小写字母接下来有两个整数分别表示添加和删除该字母的费用(空格隔开)

输出

  • 一个整数,表示把字符串变为回文串的最小费用
样例 1
输入
3 4
abcb
a 1000 1100
b 350 700
c 200 800
输出
900