考虑dp[i][g]含义为前i个数,恰好将g个0变成1的最大价值.
转移为:考虑枚举最后一段连续1的位置:
对于某个由0和1组成的串,他的得分是每段连续的1的长度的平方的总和。给定一个01串,你可以进行最多k次操作,每次操作可以选择一个0将其变成1。请问操作过后该串的最大得分是多少。
第一行两个数字n,k(1≤n≤500,0≤k≤500)分别代表字符串的长度、可以操作的次数。
第二行为仅有0,1组成的长度为n的字符串。
一个数字,代表最大得分。
输入
6 1
100101
输出
10
输出
最优的方案是将第5位的0改为1,变为100111
此时一共有两段连续的1,分别为“1”和“111‘,得分分别为1和9,总和为10。
输入
7 2
1100011
输出
20
说明
最优的方案是1111011或1101111,得分均为20。
输入
9 0
010110111
输出
14
说明
无法对字符串进行修改,此时一共有三段连续的1,长度分别为1、2、3,得分分别为1、4、9,总和为14。