是一个比较经典的区间动态规划问题,我们设置dp[l][r],即表示在字符串位置从l到的r这一段字符串全部消除能消耗掉的最大的零花钱,对于状态转移,当r=l+1是,显然直接消除,其次进行转移,我们需要对中间的字符进行枚举,即将字符串划为两段,即判断此段字符串由哪两段字符串的消除进行拼接,当然也可以视作整体进行消除,此时字符l与r进行配对消除,从dp[l+1][r-1]转移
n , k = map(int , input().split())
cost = [list(map(int , input().split())) for _ in range(k)]
s = input()
# 区间dp
小红有一个长度为n,由前k个小写字母组成的字符串(保证n为偶数)。
小美想在小红睡觉的时候把这个字符串用小红的零花钱消除干净。小美每次可以选择该串的两个相邻的字符删除,删除后将串拼上,并花掉小红一定数量的零花钱。
若某一次删除的相邻两个字符从左到右分别是a和b,则将花掉小红cost(a,b)块钱。小美希望他花掉的零花钱尽可能多,帮帮小美。
第一行有两个整数n,k(1<=n<=500,1<=k<=26),分别代表小红的字符串长度与字符串中的字符种类数(保证n为偶数且串的内容仅由前k个小写英文字母组成)。
接下来k行给出了一个k∗k的由整数构成的矩阵。矩阵中第i行第j列的元素代表消除相邻的第i个字母和第j个字母所能花掉的钱数。
最后一行有一个长度为n的字符串,代表小红的字符串。
输出一个值,代表小美最多能花掉小红多少零花钱。
输入
4 3
0 1 3
2 0 0
0 0 0
abac
输出
5
说明
如样例中先消除ab再消除ac则可花掉1+3=4元钱,先消除ba再消除ac则可花掉2+3=5元钱