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\{{sum}_i-{sum}_{j-1}|L\leq j \leq R \}$$

那么这种东西怎么维护呢?因为 $i$ 是确定的,所以 ${sum}_i$ 不变,那么其实就是求 $i \in [L-1,R-1]$ 的 ${sum}_i$ 最小值。

那么如何这个对于我们计算答案有什么用呢?我们可以考虑对于每一个 $i$,以 $i$ 为右端点的区间长度为 $[L,R]$ 的最优解就应该是 $f(i,\max(i-R+1,1),i-L+1)$。

假设第一大的三元组是 $(i,l,r)$,最优解的位置在 $j$,由于 $j$ 已经选择了,所以区间 $[l,r]$ 就被拆成了 $[l,j-1]$ 与 $[j+1,r]$ ,并且把其加入三元组,不停选出最大的三元组再重新产生新的三元组,选择 $k$ 次即可。

那么如何快速选出最大的呢?显然用堆就好了。

那么如何快速求 $f$ 呢?$RMQ$ 就好了。

Code

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇