2424. [POJ 3280]最便宜的回文

【题目描述】

给定一个仅有小写字母构成的字符串，请你通过在字符串任意位置增加或删除小写字母使其变为回文。

例如，对于字符串“abcb”，可以通过在末尾增加“a”使其变为“abcba”、或者删除字符“a”，使其变为“bcb”、或者在开头增加“bcb”，使其变为“bcbabcb”。

但是现在增加、删除每个字符的成本可能是不同的，现在请你求解将给定字符串转化为回文的最小成本。

【输入格式】

第$1$行包含两个整数$n,m(1\leq n\leq 26,1\leq m\leq 2000)$，分别表示给定成本的字符个数和字符串长度。

第$2$航给定一个字符串。

接下来$n$行，每行包含一个字符和两个整数，分别表示增加和删除该字符的成本($0\sim 10^4$)。

【输出格式】

一行一个整数，表示将原字符串变为回文的最小成本。

【样例输入】

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

【样例输出】

900

【样例说明】

若在“abcb”末尾添加一个“a”，则得到“abcba”，成本是1000；若把开头的“a”删掉，则得到“bcb”，成本是1100；若在开头插入“bcb”，则得到“bcbabcb”，成本是350+200+350=900，这是最小成本。