CF1579G Minimal Coverage 题解

有两个端点比较难受，所以考虑转化问题，找到最小的 $m$ 使得存在一个起点 $t\in [0,m]$ 使得每一步 $+a_i$ 或 $p-a_i$ 后值都在 $[0,m]$ 范围内。

显然 $m$ 是有单调性的，所以考虑二分 $m$ 的值，判定是否合法容易简单想到 $O(nm)$ 暴力背包 dp。此时总时间复杂度为 $O(nV\log V)$，其中 $V=\sum\limits_{i=1}^n a_i=O(n^2)$，即总时间复杂度为 $O(n^3\log n)$。

考虑优化。容易发现 dp 转移的形式就是对一个 $01$ 序列整体左移整体右移然后再按位与把序列框在 $[0,m]$ 范围内。因此容易想到用 bitset 简单优化做到 $O(\frac{n^3\log n}\omega)$ 求解。

但是这个时候还是过不去。考虑进一步优化，注意到答案的上界不会超过 $2\max a_i$。证明的话考虑若一个数大于 $\max a_i$ 那么下一个直接减 $a_i$ 一定不会使得上界超过 $2\max a_i$。把二分的上界改设为 $2\max a_i$ 可以做到总时间复杂度 $O(\frac{n^2\log n}\omega)$ 可以通过该题。