【bzoj2288】【POJ Challenge】生日礼物

2014年5月7日2,7610

Description

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

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

Input

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

第2行, N 个整数 A1A2, …, AN (0 ≤ |Ai| ≤ 104), 序列。

Output

一个整数,最大的和。

Sample Input


5 2
2 -3 2 -1 2

Sample Output

5

题解

如果数据范围小这题可以dp

f[i][j]表示前i个取j段这样。。

不会做于是膜拜了seter的题解

似乎是贪心的做法

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

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

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

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

如果大于m

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

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

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

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

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

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

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

这里纠结了一天。。。代码写太傻逼一直wa

学长20分钟1A了只能跪舔。

以后输入输出都写快速读入吧,似乎很优越