bzoj 2006. [NOI2010]超级钢琴 题解

Description

题目链接

给定一个长度为 n 的序列，选出 k 个长度在 [L,R] 之间的子段（不可重复），求 k 个子段和的最大值。

N\leq 500,000,k\leq 500,000,-1000\leq A_i \leq 1000,1\leq L\leq R\leq N

Solution

由于 n 十分巨大，我们不可能把所有符合条件的子段都列举出来再比较她们的大小，由于 k 比较小，于是我们需要考虑如何贪心选择最大满足的子段，选择 k 次即是答案。

定义 f(i,l,r) 表示以 i 为右端点，左端点在 [L,R] 区间内的最大子段和，{sum}_i 表示前缀和。那么显然可知：

$$f(i,l,r)=\max\