BZOJ 2288【POJ Challenge】生日礼物

作者: MayFlyyh 分类: 发布时间: 2018-09-12 23:56 ė 6 没有评论

ftiasch 18岁生日的时候,lqp18_31给她看了一个神奇的序列 A1, A2, …, AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。

自然地,ftiasch想要知道选择元素之和的最大值。你能帮助她吗?


首先,先把连续的正数负数合并,排列成正负交错的数列

此时如果有小于等于M个正数数列,那么答案就是他们的和

否则,我们维护每一项的绝对值按照从小到大排列的顺序

每次取出绝对值最小的

如果该数为正项,那么从ans中减去该数,同时与两边的负数合并后装入堆中。

删掉表示不选该数,与两边合并,使得3段变1段,同时原来两边之和的绝对值减小,保证之后的合并使最优的。

如果该数为负数,如果该数不是最左或者最右边,那么与两边的数直接合并,并且在ans中减掉该数的绝对值。

两种情况都可以使原来选的数的个数减1,并且损失的代价最小。

如果是负数并且在两边,无法合并直接丢掉,并且无法使选的数减小。

小技巧:

删除堆中指定元素

  1. 手写堆,把该元素改成正无穷或者负无穷,然后pushup或者pushdown,之后要么在最上面要么在最下面,在最下面就不管,在最上面就pop掉。

2.新开个堆,把删除的元素装入。每次检查两个堆堆顶如果相同,同时pop掉。

CODE:

#include<bits/stdc++.h>
const int N = 1e5+1e3;
int a[N],cnt,n,pre[N],m,nxt[N],sum,ans;
struct heap{
    int v,pos;
    bool operator < (const heap m) const{
        if(v!=m.v)return v>m.v;
        return pos>m.pos;
    }
    bool operator == (const heap m) const{
        return v==m.v&&pos==m.pos;
    }
};
std::priority_queue<heap> q,d;
void up(){while(!q.empty()&&!d.empty()&&q.top()==d.top())q.pop(),d.pop();}
void del(heap x){d.push(x);
up();}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i){
        int x;
        scanf("%d",&x);
        if((a[cnt]<=0&&x<=0)||(a[cnt]>=0&&x>=0)) a[cnt]+=x;
        else a[++cnt]=x;
    }
    n=cnt;
    for(int i=1;i<=n;++i){
        pre[i]=i-1,nxt[i]=i+1;
        q.push((heap){abs(a[i]),i});
        if(a[i]>0) ans+=a[i],sum++;
    }
    pre[1]=nxt[n]=0;int T=0;
//  while(!q.empty()){++T;
//      heap x=q.top();q.pop();
//      printf("%d %d %d\n",T,x.pos,x.v);
//      if(x.v==1000) break;
//  }
    while(sum>m){
        heap x=q.top();
        del(x);
        --sum;
        if(!pre[x.pos]){
            if(a[x.pos]>0){
                ans-=a[x.pos];pre[nxt[x.pos]]=0;    
                //del((heap){abs(a[nxt[x.pos]]),x.pos});
            }
            else{
                pre[nxt[x.pos]]=0;sum++;
            }
        }
        else if(!nxt[x.pos]){
            if(a[x.pos]>0){
                ans-=a[x.pos];nxt[pre[x.pos]]=0;
                //del((heap){abs(a[pre[x.pos]]),x.pos});
            }
            else{
                nxt[pre[x.pos]]=0;sum++;
            }
        }
        else {
            ans-=x.v;
            a[x.pos]+=a[nxt[x.pos]]+a[pre[x.pos]];
            del((heap){abs(a[nxt[x.pos]]),nxt[x.pos]});
            del((heap){abs(a[pre[x.pos]]),pre[x.pos]});
            nxt[pre[pre[x.pos]]]=x.pos;pre[x.pos]=pre[pre[x.pos]];
            pre[nxt[nxt[x.pos]]]=x.pos;nxt[x.pos]=nxt[nxt[x.pos]];
            q.push((heap){abs(a[x.pos]),x.pos});
        }
    }
    printf("%d\n",ans);
    return 0;
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/334

0

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部