bzoj 2288 【POJ Challenge】生日礼物 双向链表+堆优化

时间:2021-12-24 23:38:44

2288: 【POJ Challenge】生日礼物

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1003  Solved: 317
[Submit][Status][Discuss]

Description

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

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

bzoj 2288 【POJ Challenge】生日礼物 双向链表+堆优化

Input

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

第2行, N 个整数 A1, A2, ..., AN (0 ≤ |Ai| ≤ 104), 序列。

Output

一个整数,最大的和。

Sample Input

5 2
2 -3 2 -1 2

Sample Output

5

HINT

Source

是贪心的做法

首先将符号相同的一段合并成一个值,为了处理方便一开始可以将序列中的0全部去掉

如 1 3 -1 -2 4 -1 变成 4 -3 4 -1

容易证明最后结果一定是取完整的一段

如果>0的段小于m那么就解决了

如果大于m

将这些段放入堆中按绝对值进行排序

获取堆中最小值将它和周围两段合并,这里要用到双向链表

因为如果这个值是正数,那么相当于不选它了

是负数的话相当于将它左右两段合并,这样都使得选取的段数-1

但是要考虑一个边界的问题

边上的负数不能取,因为就算取了它也不存在左右两段合并

而正数可以取,相当于不选它了

 #pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue> #define pa pair<int,int>
#define ll long long
#define inf 10000007
#define N 100007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} struct cmp
{
bool operator()(pa a,pa b)
{
return abs(a.first)>abs(b.first);
}
};
priority_queue<pa,vector<pa>,cmp>q; int n,m,tot,ans,sum;
int a[N],nxt[N],pre[N];
bool mark[N]; void del(int x)
{
mark[x]=;
pre[nxt[x]]=pre[x];
nxt[pre[x]]=nxt[x];
}
int main()
{
n=read(),m=read(),tot=;
for (int i=;i<=n;i++)
{
int x=read();
if ((ll)a[tot]*x>=)a[tot]+=x;
else a[++tot]=x;
}//这里相乘比较巧妙。
n=tot;
for (int i=;i<=n;i++)
if (a[i]>) sum++,ans+=a[i];
for (int i=;i<=n;i++)
{
nxt[i]=i+;
pre[i]=i-;
q.push(make_pair(a[i],i));
}
while (sum>m)
{
sum--;
while (mark[q.top().second]) q.pop();
int x=q.top().second;q.pop();
if (pre[x]!=&&nxt[x]!=n+) ans-=abs(a[x]);
else if (a[x]>) ans-=a[x];else{sum++;continue;}
a[x]=a[pre[x]]+a[nxt[x]]+a[x];
del(pre[x]);del(nxt[x]);
q.push(make_pair(a[x],x));
}
printf("%d",ans);
}