BZOJ 2288【POJ Challenge】生日礼物

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;
}