P2048 [NOI2010] 超级钢琴题解

题意

给定一个长度为 n 的序列 a，取 k 个长度在 ql 与 qr 之间的该序列的不同的连续子段，使这 k 个子段中的元素之和最大。

思路

先对原序列计算前缀和，覆盖原数组 a，以便求子段元素和。

求前 k 大的子段元素和可以考虑贪心，即使用堆(priority_queue)，而堆中存储的是一个三元组:(u,l,r) ，表示以 u 为起始位置，末位置在 l 与 r 之间的最大子段(元素和最大的子段)。在这个三元组(u,l,r)中，我们设此最大子段的末位置为 t ，该最大子段的元素和即为 a[t]-a[u-1]，在这个堆中也以 a[t]-a[u-1] 的值为排序规则。

其中 t 的求解即为金典的静态RMQ问题，静态RMQ问题的常见解决方法有ST表，线段树，笛卡尔树等。我比较喜欢用线段树，代码如下：

CPP

struct segment{
	#define mid ((l+r)>>1)
	struct tree{
		ll z;int id;
		bool operator<(const tree&o)const{return z<o.z;}
	}tr[N<<4];
	int n;
	tree query(int u,int l,int r,int L,int R){
		if(L<=l&&r<=R)return tr[u];
		tree ans={-inf,0};
		if(L<=mid)ans=max(ans,query(u<<1,l,mid,L,R));
		if(R>mid)ans=max(ans,query(u<<1|1,mid+1,r,L,R));
		return ans;
	}tree query(int L,int R){return query(1,1,n,L,R);}
	void build(int u,int l,int r,ll *a){
		if(l==r){tr[u]={a[l],l};return ;}
		build(u<<1,l,mid,a),build(u<<1|1,mid+1,r,a);
		tr[u]=max(tr[u<<1],tr[u<<1|1]);
	}
}tree;

让我们又回到堆的问题上来。我们可以先进行预处理，将所有以 i 为起始位置，末位置在 i+ql-1 与 i+qr-1 之间的最大子段（即为所有形似(i,i+ql-1,i+qr-1)的三元组）压入堆中。再进行 k 次循环，每次将堆顶的三元组弹出并更新答案(ans)。根据堆的性质，堆顶的三元组所表示的子段就为此时剩余的子段中元素和最大的子段。在每次弹出后，我们又将三元组 (u,l,t-1) 与 (u,t+1,r) 压入堆中，这样就能完美地避免重复计算并考虑到了每种情况，具体实现如下（其中 pq 为处理 t 的函数）：

CPP

for(int i=1;i<=n-ql+1;i++)
    q.push(pq(i,i+ql-1,min(n,i+qr-1)));
while(k--){
	pq x=q.top();q.pop();
	ans+=a[x.t]-a[x.u-1];
	if(x.l<x.t)q.push(pq(x.u,x.l,x.t-1));
	if(x.t<x.r)q.push(pq(x.u,x.t+1,x.r));
}

完整代码

以下代码省略了RMQ的线段树部分：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+5,inf=2147483647;
struct segment{/*RMQ线段树*/}tree;
int n,k,ql,qr;ll a[N],ans;
struct pq{
	int u,l,r,t;
	pq(int _u=0,int _l=0,int _r=0):u(_u),l(_l),r(_r),t(tree.query(l,r).id){}
	bool operator<(const pq&o)const{return a[t]-a[u-1]<a[o.t]-a[o.u-1];}
};priority_queue<pq>q;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k>>ql>>qr,tree.n=n;
	for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
	tree.build(1,1,n,a);
	for(int i=1;i<=n-ql+1;i++)
        q.push(pq(i,i+ql-1,min(n,i+qr-1)));
	while(k--){
		pq x=q.top();q.pop();
		ans+=a[x.t]-a[x.u-1];
		if(x.l<x.t)q.push(pq(x.u,x.l,x.t-1));
		if(x.t<x.r)q.push(pq(x.u,x.t+1,x.r));
	}
	cout<<ans;
	return 0;
}

AC记录

P2048 [NOI2010] 超级钢琴题解

文章操作

题意

思路

完整代码

相关推荐

评论

P2048 [NOI2010] 超级钢琴题解