问题2122--回文

2122: 回文

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交] [状态] [讨论版] [命题人:]

题目描述

约翰在每头牛身上都安装了一个id标签（电子身份标签），当牛通过扫描仪时，系统会读取这个标签。每个id标签都是从n （1≤n ≤26）个小写字母的字母表中提取的长度为m（1≤m ≤2000）的字符串。牛有时试图通过倒退来欺骗系统。当一头牛的id标签是“abcba”时，不管它朝哪个方向走，都会读到相同的id标签，而一头牛的id标签是“abcb”时，可能会被读到两个不同的id标签（abcb和bcba）。约翰想修改牛的id标签，这样无论牛从哪个方向走过，都可以读到相同的内容。例如，“abcb”可以通过在末尾添加‘a’，形成“abcba”，这样的id标签就是回文（向前和向后读取都是相同的内容）。将id标签更改为回文的其他方法包括将“bcb”添加到开头，产生id标签“bcbabcb”；或删除字符‘a’，产生id标签“bcb”。可以在字符串中的任何位置添加或删除字符，从而生成比原始字符串长或短的字符串。给定牛的id标签及添加、删除每个字符的成本（0≤成本≤10000），求解使id标签满足回文字符串的最小成本。一个空的id标签被认为已满足要求。只有包含相关成本的字母才可以被添加到字符串中。


输入

第1行包含两个整数n 和m 。第2行包含m 个字符，表示初始的id标签。第3..n +2行的每一行都包含一个字符和两个整数，分别表示添加和删除该字符的成本。

输出

单行输出更改给定标签为回文的最小成本。

样例输入 Copy 

3 4
abcb
a 1000 1100
b 350 700
c 200 800

样例输出 Copy 

900

来源/分类

动态规划算法 区间DP 
[提交] [状态]