思路

  是一个比较经典的区间动态规划问题，我们设置dp[l][r]，即表示在字符串位置从l到的r这一段字符串全部消除能消耗掉的最大的零花钱，对于状态转移，当r=l+1是，显然直接消除，其次进行转移，我们需要对中间的字符进行枚举，即将字符串划为两段，即判断此段字符串由哪两段字符串的消除进行拼接，当然也可以视作整体进行消除，此时字符l与r进行配对消除，从dp[l+1][r-1]转移

代码

python

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$的字符串，代表小红的字符串。

输出描述

输出一个值，代表小美最多能花掉小红多少零花钱。

样例1

输入

4 3
0 1 3
2 0 0
0 0 0
abac

输出

5

说明

如样例中先消除$ab$再消除$ac$则可花掉$1+3=4$元钱，先消除$ba$再消除$ac$则可花掉$2+3=5$元钱