题解 P8049 【[COCI2010-2011#5] DVONIZ（加强版）】

· · 题解

对于 30\% 的数据，暴力枚举即可，时间复杂度 O(n^3)。

对于 50\% 的数据，加入前缀和优化即可，时间复杂度 O(n^2)。

对于 70\% 的数据：

考虑维护中间位置 \text{mid}，即对于每个 \text{mid}，找到一个最大的 x，使得该 \text{mid} 的前 x 个元素（含 \text{mid}）的和与后 x 个元素（不含 \text{mid}）的和均不大于 m，并用来更新该区间左端点的答案。

不难发现 \text{mid} 左右段的长度具有单调性，对每一个位置进行二分答案即可，时间复杂度 O(n \log n)。

但是这样的维护是不完全的，因为有的答案可能是通过上法求得最长序列的部分。又注意到对于任意一个合法序列 a，去掉 a 的第一个和最后一个元素，它依然是合法的。

于是就有如下递推式：

f_i=\max(f_{i - 1}-2,f_i)

其中 f_i 表示从第 i 个元素开始的最长的优美序列的长度，\text{DP} 即可，总时间复杂度 O(n \log n)。

对于 100\% 的数据：

注意到，当 \text{mid} 向右移动时，它能取到最远的左端点和右端点 l,r 必定也会向右边移动。那么我们就可以用双指针（尺取法）来优化。时间复杂度 O(n)。

总时间复杂度 O(n)。