【链表】BZOJ 2288: 【POJ Challenge】生日礼物

2288: 【POJ Challenge】生日礼物

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 382 Solved: 111
[Submit][Status][Discuss]

Description

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

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

Input

第1行，两个整数 N (1 ≤ N ≤ 10⁵) 和 M (0 ≤ M ≤ 10⁵), 序列的长度和可以选择的部分。

第2行， N 个整数 A₁, A₂, ..., A_N (0 ≤ |A_i| ≤ 10⁴), 序列。

Output

一个整数，最大的和。

Sample Input

5 2
2 -3 2 -1 2

Sample Output

　　先把相邻同号元素合并。

　　如果能够全选正数就全选。。

　　把所有数的绝对值入堆选前(正数个数-可选最大集合数个).

　　选正数的意义-->不选该数

　　选负数-->合并两边的正数

　　每次减掉堆顶元素的fabs即可。

　　和1150差不多的堆+链表

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #define maxn 100001

 inline int in()

 {

     int x=,f=;char ch=getchar();

     while((ch<''||ch>'')&&ch!='-')ch=getchar();

     if(ch=='-')f=-,ch=getchar();

     while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

     return f*x;

 }

 struct node{

     int x,c,ac;

     bool operator<(const node &A)const{

         return ac>A.ac;

     }

 };

 using namespace std;

 priority_queue<node>q;

 int n,k,a[maxn*],sum=,pre[maxn*],next[maxn*],nowa[maxn*],tot=,ss=;

 bool vis[maxn*];

 void solve()

 {

     int size=tot+;

     for(int i=;i<=tot;i++)q.push((node){i,nowa[i],fabs(nowa[i])});

     for(int i=;i<=ss;i++)

     {

         node Top=q.top();q.pop();

         while(vis[Top.x])Top=q.top(),q.pop();

         if(!pre[Top.x])

         {

             if(Top.c<){i--;}

             else{sum-=Top.ac;}

             vis[Top.x]=;

             pre[next[Top.x]]=;

             continue;

         }

         else if(next[Top.x]==tot+)

         {

             if(Top.c<){i--;}

             else{sum-=Top.ac;}

             vis[Top.x]=;

             next[pre[Top.x]]=tot+;

             continue;

         }

         node New;

         sum-=Top.ac;

         New.c=nowa[pre[Top.x]]+nowa[next[Top.x]]+Top.c;

         New.x=++size;

         nowa[size]=New.c;

         next[New.x]=next[next[Top.x]],pre[next[New.x]]=New.x;

         pre[New.x]=pre[pre[Top.x]],next[pre[New.x]]=New.x;

         vis[Top.x]=vis[pre[Top.x]]=vis[next[Top.x]]=;

         New.ac=fabs(New.c);

         q.push(New);

     }

 }

 void Pre()

 {

     tot=;

     for(int i=;i<=n;i++)

     {

         if(!a[i])continue;

         else if(!nowa[tot])nowa[tot]=a[i];

         else{

             if(nowa[tot]>&&a[i]>)nowa[tot]+=a[i];

             else if(nowa[tot]<&&a[i]<)nowa[tot]+=a[i];

             else nowa[++tot]=a[i];

         }

     }

     for(int i=;i<=tot;i++)next[i]=i+,pre[i]=i-;

     next[]=,pre[tot+]=tot;

 }

 int main()

 {

     n=in();k=in();

     for(int i=;i<=n;i++)a[i]=in();

     Pre();

     for(int i=;i<=tot;i++)if(nowa[i]>)ss++,sum+=nowa[i];

     if(ss<=k){printf("%d",sum);return ;}

     ss-=k;

     solve();

     printf("%d",sum);

     return ;

 }

巴特西