思路：动态规划

考虑dp[i][g]含义为前i个数，恰好将g个0变成1的最大价值.

转移为：考虑枚举最后一段连续1的位置：

case1:考虑最后连续1以i结尾，dp[i][g] = dp[j - 1][g - zero_count(arr[j:i+1])] + (j - i + 1)^2 ,

这里枚举j从i到1，zero_count(arr[j:i+1])表示j到i之间0的个数，我们需要把他们全部变为1

case2:考虑最后连续1不以i结尾，dp[i][g] = dp[i - 1][g]

这里枚举g即可。

代码

python

# 输入n和k，分别表示字符串的长度和最多可以将多少个0变为1
n, k = map(int, input().split())
# 输入字符串s
s = input()

# 初始化动态规划数组dp
# dp[i][g]表示前i个数，恰好将g个0变成1的最大价值
dp = [[0] * (k + 1) for _ in range(n + 1)]
# dp[0][k]初始化为0，表示没有数时的价值为0
dp[0][k] = 0

# 遍历每一个位置
for i in range(1, n + 1):
    zero_cnt = 0  # 统计当前连续1段中0的数量
    # 从当前i位置向前遍历
    for j in range(i, 0, -1):
        # 如果当前位置是'0'，增加0的计数
        if s[j - 1] == '0':
            zero_cnt += 1
        # 如果0的数量超过k，结束当前循环
        if zero_cnt - 1 > k:
            break
        # 遍历所有可能的g，从当前的zero_cnt到k
        for g in range(zero_cnt, k + 1):
            length = i - j + 1  # 当前段的长度
            # 更新dp[i][g]，选择最大价值
            dp[i][g] = max(dp[i][g], dp[j - 1][g - zero_cnt] + length * length)
    
    # 更新dp[i][g]，考虑不以i结尾的情况
    for g in range(k + 1):
        dp[i][g] = max(dp[i][g], dp[i - 1][g])

# 输出最终结果，前n个数，恰好将k个0变为1的最大价值
print(dp[n][k])

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

对于某个由$0$和$1$组成的串，他的得分是每段连续的$1$的长度的平方的总和。给定一个$01$串，你可以进行最多k次操作，每次操作可以选择一个$0$将其变成$1$。请问操作过后该串的最大得分是多少。

输入描述

第一行两个数字$n,k$($1≤n≤500，0≤k≤500$)分别代表字符串的长度、可以操作的次数。

第二行为仅有$0,1$组成的长度为$n$的字符串。

输出描述

一个数字，代表最大得分。

样例1

输入

6 1
100101

输出

10

输出

最优的方案是将第$5$位的$0$改为1，变为100111

此时一共有两段连续的$1$,分别为“$1$”和“$111$‘,得分分别为$1$和$9$,总和为$10$。

样例2

输入

7 2
1100011

输出

20

说明

最优的方案是1111011或1101111，得分均为20。

样例3

输入

9 0
010110111			

输出

14

说明

无法对字符串进行修改，此时一共有三段连续的$1$,长度分别为$1、2、3$，得分分别为$1、4、9$，总和为$14$。