你是不是觉得跟数列分段 II 这题很像:https://www.wikioi.cn/problem/30014
然后你是不是过了样例 然后只有20分,哈哈哈
本题 可以为负数,显然原来的贪心策略就假掉了
首先有一个重要结论:如果我们要求每段的和 不超过 的情况下,最少可以划分成 段, 最多可以划分成 段,那么这个数组每段和不超过 的情况下,我们可以划分出 中的任意段。
如果上述结论正确,那么显然我们可以继续 二分答案 , 因为 不超过成包含关系,每次二分答案只需要计算出最少的段数 和 最多的段数 ,
最后只需要判断 是否满足要求即可, 求最少的段数 和 最多的段数 可以做一个线性DP,然后用 线段树/树状数组 优化到 O(nlogn), 结合二分,最终时间复杂度带2个log
接下来说明上述结论的正确: (信息学更多需要猜出正确的结论,虽然这个结论第二眼看看很假)
考虑一个dp的过程,假设为原数组, 为前缀和
归纳假设已经知道了表示前个元素构成的子序列可以划分的段数范围
假设我们已经求出了
现在求
如果要让最终结果 不是一个区间 (最终我们会证明这个并不成立)
那么假设我们dp枚举从到枚举的话,肯定会出现一个,使得并上之前还是一个区间,并上去之后不是了
假设当前是
并且这个 是由某个 () 提供的, 这个s[k]应该要满足 , 否则肯定可以把最后一段合并,找到更小的。
如果的话,
那的最多是的
也就是说我们当前的是"k的L"+1,也就是最多的+2
然后这次更新的是的, 刚好连起来了
然后你再仔细想想,因为这个结论的说明cls也是问人的,有点糊了,如果你理解了,记得给cls来解释一遍。