2288: 【POJ Challenge】生日礼物
Description
ftiasch 18岁生日的时候，lqp18_31给她看了一个神奇的序列 A1, A2, ..., AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。
自然地，ftiasch想要知道选择元素之和的最大值。你能帮助她吗？
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 2Sample Output
5HINT
Source
【分析】
我好笨啊。。。
首先可以把序列弄的好看点，0删掉，负数一段合并，正数一段合并。
那么就是- + - + - 交替。
假设我们先把所有正段选了。假设选了cnt段。
如果cnt<=m，那么这显然就是答案。
否则，按照他们的绝对值扔进小根堆里面，每次选队顶元素。ans-=他的值。
如果选到正数，表示把这个正数删掉，就少了一段。
如果选到负数，表示把负数两边的两段连起来，也少了一段。
知道这个意思之后就知道两端的负数是不可以选的，因为没有意义。
然后删掉那个数之后和两边的两段合并起来重新扔到堆里面做。。【里面包含后悔操作！！！！思考一下！！！！
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 100100 struct node
{
int id,x;
friend bool operator < (node x,node y)
{
return x.x>y.x;
}
}; priority_queue<node > q; int a[Maxn],w[*Maxn];
int lt[*Maxn],nt[*Maxn];
bool mark[*Maxn]; int myabs(int x) {return x<?-x:x;} int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
w[]=a[];
int p=;
for(int i=;i<=n;i++)
{
if(a[i]==) continue;
if((a[i]>=&&w[p]>=)||(a[i]<=&&w[p]<=)) w[p]+=a[i];
else w[++p]=a[i];
}
int cnt=,ans=;
for(int i=;i<=p;i++) if(w[i]>) cnt++,ans+=w[i];
if(cnt>m)
{
m=cnt-m;
memset(mark,,sizeof(mark));
while(!q.empty()) q.pop();
for(int i=;i<=p;i++) nt[i]=i+;nt[p]=-;
for(int i=;i<=p;i++) lt[i]=i-;
for(int i=;i<=p;i++)
{
node xx;
xx.id=i;
xx.x=myabs(w[i]);
q.push(xx);
}
cnt=p;
for(int i=;i<=m;i++)
{
while(mark[q.top().id]) q.pop();
node xx=q.top();q.pop();
if(lt[xx.id]==)
{
lt[nt[xx.id]]=;
if(w[xx.id]<)
{
i--;
continue;
}
ans-=xx.x;
}
else if(nt[xx.id]==-)
{
nt[lt[xx.id]]=-;
if(w[xx.id]<)
{
i--;
continue;
}
ans-=xx.x;
}
else
{
ans-=xx.x;
mark[lt[xx.id]]=mark[nt[xx.id]]=;
cnt++;
nt[lt[lt[xx.id]]]=lt[nt[nt[xx.id]]]=cnt;
lt[cnt]=lt[lt[xx.id]];nt[cnt]=nt[nt[xx.id]];
node nw;
nw.id=cnt;
nw.x=myabs(w[nt[xx.id]]+w[lt[xx.id]]+w[xx.id]);
w[cnt]=w[nt[xx.id]]+w[lt[xx.id]]+w[xx.id];
q.push(nw);
}
}
}
printf("%d\n",ans);
return ;
}
给一个sample in：
5
53 -20 3 -27 68 out:
77
发发表情更健康
2017-01-14 11:01:57