BZOJ 2288 【POJ Challenge】生日礼物（贪心+优先队列）

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2288

【题目大意】

　　给出一列数，求最多取m段连续的数字，使得总和最大

【题解】

　　首先我们对数据进行合并处理，连续的一段正数或者连续的一段负数处理成一个数字，
　　之后我们发现，如果正数的个数小于等于m，那么直接输出正数的总和即可，
　　如果大于m，我们有些正数不选，或者选择一些负数把左右两端的正数并起来。
　　这个负数的选择过程相当于减去这个数的绝对值，
　　正数选择拿出去的过程也相当于减去这个数的绝对值，
　　在选择一个负数合并的过程中，两边的正数必须是没有被操作过的，
　　同样，选择一个正数删去的过程中，两边的负数肯定也必须是没有操作过的，
　　那么问题就转化为，给你一些数，请你选择其中k个不相邻的数，使得其和最小，
　　等同于BZOJ 1150 [CTSC2007]数据备份Backup

【代码】

#include <cstdio>

#include <algorithm>

#include <queue>

using namespace std;

typedef pair<int,int> P;

const int N=100010;

const int INF=0x3f3f3f3f;

int n,m,a[N],b[N],l[N],r[N];

int main(){

    while(~scanf("%d%d",&n,&m)){

        for(int i=1;i<=n;i++)scanf("%d",&a[i]);

        while(a[n]<=0)n--;int st=1;

        while(a[st]<=0)st++;

        int cnt=0,ans=0;

        for(;st<=n;st++){if(!((a[st]>0)^(a[st-1]>0)))b[cnt]+=a[st];else b[++cnt]=a[st];}

        for(int i=1;i<=cnt;i++)if(b[i]>0){ans+=b[i];m--;}else b[i]=-b[i];

        if(m>=0){printf("%d\n",ans);continue;}

        priority_queue<P,vector<P>,greater<P> >Q;

        for(int i=1;i<=cnt;i++)l[i]=i-1,r[i]=i+1,Q.push(P(b[i],i));

        r[cnt]=0;

        for(int i=1;i<=-m;i++){

            while(b[Q.top().second]!=Q.top().first)Q.pop();

            int x=Q.top().second;Q.pop();

            ans-=b[x];

            if(!l[x]){b[r[x]]=INF;l[r[x]]=0;}

            else if(!r[x]){b[l[x]]=INF;r[l[x]]=0;}

            else{

                b[x]=b[l[x]]+b[r[x]]-b[x];

                b[l[x]]=b[r[x]]=INF;

                r[l[x]=l[l[x]]]=l[r[x]=r[r[x]]]=x;

                Q.push(P(b[x],x));

            }

        }printf("%d\n",ans);

    }return 0;

}

巴特西

BZOJ 2288 【POJ Challenge】生日礼物（贪心+优先队列）

最新文章

热门文章