会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
思路
是一个比较经典的区间动态规划问题，我们设置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()
