阻断元素 题解

思路

二分一个候选代价 $x$。我们需要判断能否选出若干阻断位置，使被阻断元素之和不超过 $x$，并且任意两个相邻阻断位置之间以及首尾两端的未阻断连续段之和都不超过 $x$。

记前缀和为 $s_i=\sum_{k=1}^i a_k$。令 $dp_i$ 表示把位置 $i$ 阻断，并且已经合法处理前 $i$ 个位置时，被阻断元素和的最小值；另设虚拟位置 $0$，$dp_0=0$。若上一个阻断位置为 $j<i$，则中间段合法当且仅当

于是

最后还要检查尾段，即在所有满足 $s_n-s_j\le x$ 的 $j$ 中，是否存在 $dp_j\le x$。

做法

子任务 1 枚举阻断位置集合，直接计算阻断元素和与所有未阻断连续段之和，取最小值。复杂度为 $O(2^n n)$。

子任务 2 对每个 $i$ 枚举所有 $j<i$ 完成上述转移。一次判定为 $O(n^2)$，配合二分的总复杂度为 $O(n^2\log S)$，其中 $S=\sum a_i$。

完整做法利用 $a_i>0$，因此前缀和严格递增。对每个 $i$，合法的 $j$ 构成一个随 $i$ 右移的连续后缀。用单调队列维护窗口内 $dp_j$ 的最小值，一次判定为 $O(n)$。

复杂度

二分区间可取 $[-1,S]$：$S$ 一定可行，而 $-1$ 一定不可行。总时间复杂度为 $O(n\log S)$，空间复杂度为 $O(n)$。所有前缀和与 DP 值必须使用 64 位整数。

正确性说明

任意合法方案按阻断位置顺序，都对应 DP 中从虚拟位置 $0$ 出发的一条转移链；转移条件恰好保证两个相邻阻断位置之间的段和不超过 $x$，转移代价之和恰好是阻断元素之和。反之，任意 DP 转移链都给出一组满足所有内部段限制的阻断位置；最终尾段检查补齐最后一段。因此判定等价于存在代价不超过 $x$ 的方案。

可行性关于 $x$ 单调，故二分得到的最小可行值就是答案。