【链表】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差不多的堆+链表

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<queue>
 6 
 7 #define maxn 100001
 8 
 9 inline int in()
10 {
11     int x=0,f=1;char ch=getchar();
12     while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
13     if(ch=='-')f=-1,ch=getchar();
14     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
15     return f*x;
16 }
17 
18 struct node{
19     int x,c,ac;
20     bool operator<(const node &A)const{
21         return ac>A.ac;
22     }
23 };
24 
25 using namespace std;
26 
27 priority_queue<node>q;
28 
29 int n,k,a[maxn*5],sum=0,pre[maxn*5],next[maxn*5],nowa[maxn*5],tot=0,ss=0;
30 
31 bool vis[maxn*5];
32 
33 void solve()
34 {
35     int size=tot+1;
36     for(int i=1;i<=tot;i++)q.push((node){i,nowa[i],fabs(nowa[i])});
37     for(int i=1;i<=ss;i++)
38     {
39         node Top=q.top();q.pop();
40         while(vis[Top.x])Top=q.top(),q.pop();
41         if(!pre[Top.x])
42         {
43             if(Top.c<0){i--;}
44             else{sum-=Top.ac;}
45             vis[Top.x]=1;
46             pre[next[Top.x]]=0;
47             continue;
48         }
49         else if(next[Top.x]==tot+1)
50         {
51             if(Top.c<0){i--;}
52             else{sum-=Top.ac;}
53             vis[Top.x]=1;
54             next[pre[Top.x]]=tot+1;
55             continue;
56         }
57         node New;
58         sum-=Top.ac;
59         New.c=nowa[pre[Top.x]]+nowa[next[Top.x]]+Top.c;
60         New.x=++size;
61         nowa[size]=New.c;
62         next[New.x]=next[next[Top.x]],pre[next[New.x]]=New.x;
63         pre[New.x]=pre[pre[Top.x]],next[pre[New.x]]=New.x;
64         vis[Top.x]=vis[pre[Top.x]]=vis[next[Top.x]]=1;
65         New.ac=fabs(New.c);
66         q.push(New);
67     }
68 }
69 
70 void Pre()
71 {
72     tot=1;
73     for(int i=1;i<=n;i++)
74     {
75         if(!a[i])continue;
76         else if(!nowa[tot])nowa[tot]=a[i];
77         else{
78             if(nowa[tot]>0&&a[i]>0)nowa[tot]+=a[i];
79             else if(nowa[tot]<0&&a[i]<0)nowa[tot]+=a[i];
80             else nowa[++tot]=a[i];
81         }
82     }
83     for(int i=1;i<=tot;i++)next[i]=i+1,pre[i]=i-1;
84     next[0]=1,pre[tot+1]=tot;
85 }
86 
87 int main()
88 {
89     n=in();k=in();
90     for(int i=1;i<=n;i++)a[i]=in();
91     Pre();
92     for(int i=1;i<=tot;i++)if(nowa[i]>0)ss++,sum+=nowa[i];
93     if(ss<=k){printf("%d",sum);return 0;}
94     ss-=k;
95     solve();
96     printf("%d",sum);
97     return 0;
98 }

View Code