【bzoj2006】[NOI2010]超级钢琴

2015.04.15 14:37 Wed | 3次阅读 | 旧日oi | 固定链接 | 源码

Description

小Z是一个小有名气的钢琴家,最近C博士送给了小Z一架超级钢琴,小Z希望能够用这架钢琴创作出世界上最美妙的音乐。 这架超级钢琴可以弹奏出n个音符,编号为1至n。第i个音符的美妙度为Ai,其中Ai可正可负。 一个“超级和弦”由若干个编号连续的音符组成,包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的,当且仅当这两个超级和弦所包含的音符集合是相同的。 小Z决定创作一首由k个超级和弦组成的乐曲,为了使得乐曲更加动听,小Z要求该乐曲由k个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最大值是多少。

Input

第一行包含四个正整数n, k, L, R。其中n为音符的个数,k为乐曲所包含的超级和弦个数,L和R分别是超级和弦所包含音符个数的下限和上限。 接下来n行,每行包含一个整数Ai,表示按编号从小到大每个音符的美妙度。

Output

只有一个整数,表示乐曲美妙度的最大值。

Sample Input

4 3 2 3
3
2
-6
8

Sample Output

11
【样例说明】
共有5种不同的超级和弦:
音符1 ~ 2,美妙度为3 + 2 = 5
音符2 ~ 3,美妙度为2 + (-6) = -4
音符3 ~ 4,美妙度为(-6) + 8 = 2
音符1 ~ 3,美妙度为3 + 2 + (-6) = -1
音符2 ~ 4,美妙度为2 + (-6) + 8 = 4
最优方案为:乐曲由和弦1,和弦3,和弦5组成,美妙度为5 + 2 + 4 = 11。

题解

复习的时候又发现了这道题,当时没写题解,现在补上吧
我们维护出一个前缀和,这样一段区间[l,r]的美妙度之和就等于sum[r]-sum[l-1]
我们先枚举一下区间的起点,那么以这个点为起点的超级和弦的终点一定在i+l-1到i+r-1之间,而找其中的最大值我们可以用RMQ解决,这样搞出一个四元组(i,i+l-1,i+r-1,id),id是区间中最大值所在位置,把这东西扔到优先队列里,排序方法就是按sum[id]-sum[i]从小到大排,这样每次弹出队尾都是当前最大和弦。
弹出一个和弦之后,我们累加答案,然后因为这段区间中id那个点已经用不了了,所以我们可以以id那个点为中心,把区间分成两段,对每段再求一次最大值所在位置,重新加入优先队列,这样可以保证最优
时间复杂度nlogn,或许会达到(n+k)log n
维护一个优先队列,每次插入