2006: [NOI2010]超级钢琴
Time Limit: 20 Sec Memory Limit: 552 MB
Submit: 1842 Solved: 901
[Submit][Status][Discuss]
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
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。
【样例说明】
共有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。
HINT
Source
很久以前遗留下来的一道题了。。。记得AK爷几个月前就已经轻松AK了。。%%%
原来印象中是一道神题。。现在自己打了一下因为long longWA了一次。。其他感觉也还好。。然而因为整个人沉浸在英语爆蛋的悲哀中
。。这么短短的代码打了一个来小时。。手写堆也打错了。。
具体的方法是我们对原来序列每一个点维护一个五元组\([i,x,y,val,pos]\)，i表示序列的开头位置，x，y表示序列的左右边界，val表示i这个点到x到y这一段区间中和最大的值，pos表示和最大的位置，将所有位置的五元组加入堆中，按val从大到小排序。
然后每一次从中取出一个最大值，然后将他表示的区间拆成两段\([1,x,pos-1,newval,newpos]\)和\([i,pos+1,y,newval,newpos]\)，加入堆中。。直到取出K个元素结束
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const ll N = 1500010;
struct data{ll val,id;} next;
struct Tree{ll l,r;data Max;} tree[N<<2];
struct node{ll fis,l,r,val,pos;};
bool operator > (data a,data b){return a.val>b.val;}
bool operator < (data a,data b){return a.val<b.val;}
bool operator < (node a,node b){return a.val<b.val;}
bool operator > (node a,node b){return a.val>b.val;}
struct Heap{
node hp[N];
ll cnt;
void Up(ll pos){
while (pos>1 && hp[pos]>hp[pos>>1]){
swap(hp[pos],hp[pos>>1]);
pos>>=1;
}
}
void Down(ll pos){
for (ll p=pos;;){
if ((pos<<1)<=cnt && hp[pos<<1]>hp[p]) p = pos<<1;
if ((pos<<1|1)<=cnt && hp[pos<<1|1]>hp[p]) p = pos<<1|1;
if (p==pos) return;
swap(hp[pos],hp[p]);
pos = p;
}
}
void push(ll fis,ll l,ll r,ll val,ll pos){
hp[++cnt] = (node){fis,l,r,val,pos};
Up(cnt);
}
void pop(){hp[1] = hp[cnt--];Down(1);}
node top(){return hp[1];}
} Q;
ll n,K,L,R,a[N],ans;
ll read(){
ll x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
void Build(ll pos,ll l,ll r){
tree[pos].l = l;tree[pos].r = r;
if (l==r){tree[pos].Max = (data){a[l],l};return;}
ll mid = (l+r)>>1;
Build(pos<<1,l,mid);Build(pos<<1|1,mid+1,r);
if (tree[pos<<1].Max>tree[pos<<1|1].Max) tree[pos].Max = tree[pos<<1].Max;
else tree[pos].Max = tree[pos<<1|1].Max;
}
data Query(ll pos,ll l,ll r){
if (tree[pos].l==l && tree[pos].r==r) return tree[pos].Max;
ll mid = (tree[pos].l+tree[pos].r)>>1;
if (r<=mid) return Query(pos<<1,l,r);
else if (l>mid) return Query(pos<<1|1,l,r);
else {
data res1 = Query(pos<<1,l,mid),res2 = Query(pos<<1|1,mid+1,r);
if (res1>res2) return res1;
else return res2;
}
}
int main(){
n = read();K = read();L = read();R = read();
for (ll i=1;i<=n;i++) a[i] = a[i-1]+read();
Build(1,1,n);
for (ll i=1;i<=n-L+1;i++){
data now = Query(1,i+L-1,min(n,i+R-1));
Q.push(i,i+L-1,min(n,i+R-1),now.val-a[i-1],now.id);
}
for (ll i=1;i<=K;i++){
node now = Q.top();Q.pop();
ans+=now.val;
if (now.l!=now.pos){
next = Query(1,now.l,now.pos-1);
Q.push(now.fis,now.l,now.pos-1,next.val-a[now.fis-1],next.id);
}
if (now.r!=now.pos){
next = Query(1,now.pos+1,now.r);
Q.push(now.fis,now.pos+1,now.r,next.val-a[now.fis-1],next.id);
}
}
printf("%lld",ans);
}
评论 (0)
