含负能量球的取球操作最大能量和问题（无法用常规贪心）

由于存在负能量球，常规贪心策略（比如只取最大的几个球）不适用，我们可以通过枚举所有可能的取球组合+利用多余操作移除负能量球来找到最优解，具体思路如下：

1. 核心观察：

   • 操作III和IV允许我们将手中的球放回队列，每次放回消耗1次操作。因此，当我们用m次操作取了m个球后（m ≤ min(k, n)），剩余的k - m次操作可以用来移除手中的负能量球（最多移除k - m个，或所有手中的球）。
   • 最优策略可转化为：枚举所有从左侧取i个、右侧取j个的组合（i + j ≤ k，且i + j ≤ n），计算这些球的总和，再用剩余操作移除其中最小的s个球（s ≤ k - (i+j)），取所有情况中的最大值。

2. 步骤分解：

   • 预处理前缀和与后缀和数组，快速计算取左侧i个、右侧j个球的总和。
   • 枚举所有合法的i（0 ≤ i ≤ min(k, n)）和j（0 ≤ j ≤ min(k - i, n - i)）。
   • 收集当前取到的i+j个球的所有值，排序后计算其前缀和，方便快速获取前s个最小值的总和。
   • 计算当前组合下，移除0到min(k - (i+j), i+j)个最小值后的总和，记录最大值。
   • 最终结果需考虑“不取任何球”的情况（总和为0），避免所有球均为负能量时得到负数结果。

n, k = map(int, input().split())
v = list(map(int, input().split()))

# 预处理前缀和：prefix[i] 表示取前i个球的总和
prefix = [0] * (n + 1)
for i in range(1, n+1):
    prefix[i] = prefix[i-1] + v[i-1]

# 预处理后缀和：suffix[j] 表示取后j个球的总和
suffix = [0] * (n + 1)
for j in range(1, n+1):
    suffix[j] = suffix[j-1] + v[n - j]

max_total = 0  # 初始化为0，对应不取任何球的情况

# 枚举左侧取i个，右侧取j个的所有可能
for i in range(0, min(k, n) + 1):
    # 剩余操作次数最多能取j个，且i+j不能超过n
    max_j = min(k - i, n - i)
    for j in range(0, max_j + 1):
        total_ops = i + j
        if total_ops == 0:
            continue  # 已经考虑过不取的情况
        # 取到的所有球
        balls = v[:i] + (v[n-j:] if j > 0 else [])
        # 排序，方便取最小的s个
        balls.sort()
        # 计算balls的前缀和，prefix_balls[s]是前s个最小值的和
        prefix_balls = [0] * (len(balls) + 1)
        for s in range(1, len(balls)+1):
            prefix_balls[s] = prefix_balls[s-1] + balls[s-1]
        # 最多可以移除s个球，s的范围是0到min(k - total_ops, len(balls))
        max_remove = min(k - total_ops, len(balls))
        for s in range(0, max_remove + 1):
            current_sum = (prefix[i] + suffix[j]) - prefix_balls[s]
            if current_sum > max_total:
                max_total = current_sum

print(max_total)

内容的提问来源于stack exchange，提问作者user27379311