题目内容

小红有一个长度为$n$，由前$k$个小写字母组成的字符串(保证$n$为偶数)。

小美想在小红睡觉的时候把这个字符串用小红的零花钱消除干净。小美每次可以选择该串的两个相邻的字符删除，删除后将串拼上，并花掉小红一定数量的零花钱。

思路

  是一个比较经典的区间动态规划问题，我们设置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