生日礼物

Time Limit: 10 Sec Memory Limit: 128 MB

Description

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

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

Input

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

第2行， N 个整数 A1, A2, …, AN , 序列。

Output

一个整数，最大的和。

Sample Input

5 2
　2 -3 2 -1 2

Sample Output

5

HINT

1 ≤ N ≤ 105， 0 ≤ M ≤ 105， 0 ≤ |Ai| ≤ 104

Solution

首先，我们可以把权值正负相同的连续的一段合并起来。Ans+=（所有正数），块数++。

然后把每一段的绝对值加入到小根堆里面。每次贪心取出最小的来，块数减去 1 直到满足题目要求为止。

为什么这样可以对呢？我们来讨论一下：

1. 如果删去的段是正数， 那么相当于不取这个。

2. 如果删去的段是负数，那么相当于取了这个段合并它左右的两个段。

但是！这样会有一个问题！就是无法考虑连续取5个段及以上的情况，并且无法保证：取了一个数不取相连的两个数（会导致块数不减）。

所以判断一下，每次取段的时候，删去左右两个小段，加上一个大段（他们三个合并的值）即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 200005;
const int INF = 1000000007;

int n, m;
int a[ONE], A[ONE];
int pre[ONE], suc[ONE];
int Ans, block;

struct power
{
    int id, val;
    bool operator <(power a) const
    {
        return a.val < val;
    }
};
priority_queue <power> q;

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}


int main()
{
    n = get();    m = get();
    for(int i = 1; i <= n; i++) a[i] = get();
    int from = 1;    while(a[from] <= 0) from++;
    int to = n;        while(a[to] <= 0) to--;

    n = 0;
    for(;from <= to;)
    {
        if( (a[from-1] <= 0 && a[from] <= 0) || (a[from-1] > 0 && a[from] > 0))
            A[n] += a[from];
        else A[++n] = a[from];
        from++;
    }

    for(int i = 1; i <= n; i++)
    {
        pre[i] = i - 1;
        suc[i] = i + 1;
        if(A[i] > 0) Ans += A[i], block++;
        A[i] = abs(A[i]);
        q.push( (power){i, A[i]} );
    }

    if(block <= m) {printf("%d", Ans); return 0;}

    pre[1] = suc[n] = 0;

    for(;;)
    {
        for(;;)
        {
            power u = q.top();
            if(u.val != A[u.id]) q.pop();
            else break;
        }

        power u = q.top();    q.pop();
        Ans -= u.val;

        if(pre[u.id] == 0)    A[suc[u.id]] = INF, pre[suc[u.id]] = 0;
        else
            if(suc[u.id] == 0)    A[pre[u.id]] = INF, suc[pre[u.id]] = 0;
        else
        {
            A[u.id] = A[pre[u.id]] + A[suc[u.id]] - A[u.id];
            A[pre[u.id]] = A[suc[u.id]] = INF;
            pre[u.id] = pre[pre[u.id]];
            suc[u.id] = suc[suc[u.id]];
            pre[suc[u.id]] = suc[pre[u.id]] = u.id;
            q.push( (power){u.id, A[u.id]} );
        }

        block--;    if(block <= m) break;
    }

    printf("%d", Ans);
}