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

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#define LL long long 
using namespace std;
#define ig(x) ('0'<=(x)&&(x)<='9')
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(!ig(ch)) f=ch=='-'?-1:f,ch=getchar();
	while(ig(ch)) res=(res<<3)+(res<<1)+(ch&15),ch=getchar();
	return res*f;
}
#undef ig
inline void write(LL x){
	if(x<0) putchar('-'),x=-x;
	x<10?putchar(x+'0'):(write(x/10),putchar(x%10+'0'));
}
int N,K,L,R,sum[500010],Log[500010],mx[500010][30];
LL ans;
struct node{int i,l,r,t;};
#define mkp(a,b,c,d) ((node){(a),(b),(c),(d)})
inline bool operator<(const node& x,const node& y){return sum[x.t]-sum[x.i-1]<sum[y.t]-sum[y.i-1];}
priority_queue<node,vector<node> > q;
inline int rmq(){
	Log[0]=-1;
	for(int i=1;i<=N;i++) Log[i]=Log[i>>1]+1;
	int t=Log[N];
	for(int i=1;i<=N;i++) mx[i][0]=i;
	for(int i=N;i>=1;i--){
		for(int j=1;j<=t;j++){
			if(i+(1<<j)-1>N) break ;
			int t1=mx[i][j-1],t2=mx[i+(1<<j-1)][j-1];
			mx[i][j]=sum[t1]>sum[t2]?t1:t2;
		}
	}
}
inline int get(int l,int r){
	if(l==r) return l;
	int t=Log[r-l+1],t1=mx[l][t],t2=mx[r-(1<<t)+1][t];
	return sum[t1]>sum[t2]?t1:t2;
}
int main(){
	N=read(),K=read(),L=read(),R=read();
	for(int i=1,x;i<=N;i++) x=read(),sum[i]=sum[i-1]+x;
	rmq();
	for(int i=1,r;i+L-1<=N;i++) r=min(i+R-1,N),q.push(mkp(i,i+L-1,r,get(i+L-1,r)));
	for(int i=1;i<=K;i++){
		node u=q.top();q.pop();
		ans+=sum[u.t]-sum[u.i-1];
		if(u.t-1>=u.l) q.push(mkp(u.i,u.l,u.t-1,get(u.l,u.t-1)));
		if(u.t+1<=u.r) q.push(mkp(u.i,u.t+1,u.r,get(u.t+1,u.r)));
	}
	return write(ans),0;
}
暂无评论

发送评论 编辑评论


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