对于某个由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。
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.