BZOJ2288 【POJ Challenge】生日礼物 【堆 + 链表】

题目

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

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

输入格式

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

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

输出格式

一个整数，最大的和。

输入样例

5 2

2 -3 2 -1 2

输出样例

5

题解

我们把连续的同号元素合并
得到的序列就是正负交错的序列

加入正数数量<=m，全部选掉就是答案

若正数数量>m，就对于某些数意味着
①不选该正数
②多选一个负数使得相邻正数相连，这样相当于可以少放弃一个正数

我们先将正数总和求出来
然后将所有数的绝对值加入小根堆
每次选出一个减去，然后与邻近的合并【就像选m个不相邻的数和最小一样】

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
#define ls (u << 1)
#define rs (u << 1 | 1)
#define fa (u >> 1)
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
inline int read(){
    int out = 0,flag = 1; char c = getchar();
    while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
    while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
    return out * flag;
}
int pre[maxn],nxt[maxn],val[maxn],n,m,A[maxn],V[maxn],tot,cnt;
struct node{int v,u;}H[2 * maxn];
int hsiz,pos[2 * maxn];
int pd(int u){
    int small;
    while (true){
        small = u;
        if (ls <= hsiz && H[ls].v < H[small].v) small = ls;
        if (rs <= hsiz && H[rs].v < H[small].v) small = rs;
        if (small != u){
            pos[H[small].u] = u; pos[H[u].u] = small;
            swap(H[small],H[u]);
            u = small;
        }else break;
    }
    return u;
}
void pup(int u){
    while (u > 1 && H[fa].v > H[u].v){
        pos[H[fa].u] = u; pos[H[u].u] = fa;
        swap(H[fa],H[u]);
        u = fa;
    }
}
void ins(int u){
    H[++hsiz] = (node){val[u],u}; pos[hsiz] = u;
    pup(hsiz);
}
void del(int u){
    pos[H[hsiz].u] = u;
    swap(H[u],H[hsiz--]);
    u = pd(u);
    pup(u);
}
int main(){
    n = read(); m = read();
    REP(i,n){
        A[++tot] = read();
        if (!A[tot]) tot--;
    }
    int x = 1;
    while (A[x] < 0 && x <= tot) x++;
    if (x > tot) {puts("0"); return 0;}
    V[n = 1] = A[x];
    while (A[tot] < 0 && tot) tot--;
    if (!tot) {puts("0"); return 0;}
    for (int i = x + 1; i <= tot; i++){
        if ((A[i] < 0 && A[i - 1] < 0) || (A[i] > 0 && A[i - 1] > 0))
            V[n] += A[i];
        else V[++n] = A[i];
    }
    cnt = n / 2 + 1;
    if (cnt <= m){
        sort(V + 1,V + 1 + n);
        int ans = 0;
        for (int i = 0; i < cnt && V[n - i] > 0; i++) ans += V[n - i];
        printf("%d\n",ans);
    }else {
        int ans = 0;
        for (int i = 1; i <= n; i++){
            if (V[i] > 0) ans += V[i];
            val[i] = abs(V[i]);
            if (i > 1) pre[i] = i - 1;
            if (i < n) nxt[i] = i + 1;
            ins(i);
        }
        int t = cnt - m,x; node u;
        while (t--){
            u = H[1]; x = u.u;
            ans -= u.v;
            if (!pre[x]){
                del(1); del(pos[nxt[x]]);
                pre[nxt[nxt[x]]] = 0;
            }else if (!nxt[x]){
                del(1); del(pos[pre[x]]);
                nxt[pre[pre[x]]] = 0;
            }else {
                int l = pre[x],r = nxt[x];
                del(pos[l]); del(pos[r]);
                H[1].v = val[x] = val[l] + val[r] - val[x]; pos[x] = 1;
                pd(1);
                nxt[pre[x] = pre[l]] = x;
                pre[nxt[x] = nxt[r]] = x;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}