评分保护线 题解

思路

记前缀和为 $p_0=0,p_i=\sum_{j=1}^i a_j$。固定 $k$ 后，在第一次达到 $k$ 之前评分就是普通前缀和；保护生效后，每次跌破 $k$ 都会被抬回 $k$。

若第一次达到 $k$ 的位置为 $j$，最终评分相对总和 $p_n$ 的提升为

对固定的首次到达位置，提升随 $k$ 增大，因此只需考虑某个前缀峰值 $p_j$。最终要最大化“前缀值减去其后缀中的最小前缀和”。

做法

子任务 1：整数保护线穷举

在 $n\le10,|a_i|\le10$ 时，最优行为一定能由 $[\min p_i-1,\max p_i+1]$ 内的某个整数代表。枚举这些 $k$ 并直接模拟全部比赛。

子任务 2：前缀候选模拟

最优保护线可取某个前缀和，另加一个“高于所有前缀、永不生效”的候选。枚举 $O(n)$ 个候选并各自模拟 $O(n)$ 次比赛。

子任务 3：最大回撤

从右向左维护 $mn=\min_{r\ge i}p_r$，计算每个位置的 $p_i-mn$，取差值最大的 $p_i$ 作为 $k$。这就是能由保护线弥补的最大后续回撤。

复杂度

三个层级的单组时间复杂度分别为 $O(n^2\max|a_i|)$、$O(n^2)$ 和 $O(n)$；前两者空间复杂度为 $O(n)$，满分算法也使用 $O(n)$ 前缀和空间。多组数据按 $n$ 的总和计算。

正确性证明

引理 1　若 $k$ 首次在位置 $j$ 被达到，最终评分为 $p_n+\max(0,k-\min_{r\ge j}p_r)$。

证明　保护生效前没有修正。生效后，所有低于 $k$ 的最低偏移会被整体补回；所需总补偿正是 $k$ 超过后续最低前缀和的部分。∎

引理 2　存在一个最优 $k$ 等于某个前缀和 $p_i$，或高于所有前缀而从不生效。

证明　保持首次到达位置不变时，引理 1 中的目标关于 $k$ 单调不减，因此可把 $k$ 提高到该位置的前缀值。若始终未到达，则所有这类 $k$ 都得到未经保护的总和。∎

定理　最大回撤算法输出的 $k$ 最优。

证明　由引理 2 只需比较前缀候选。对候选 $p_i$，引理 1 给出的最大提升正是 $p_i-\min_{r\ge i}p_r$ 的非负部分。算法枚举并最大化了全部这些差值，因此对应最终评分不小于任何其他 $k$。∎