https://molmin.github.io/OI/problem/roi49s/solution

贪心 & 优先队列 & 链表

容易发现连续的同号段可以合并在一起，与原问题等价。于是此时整个序列就变成正负交替的序列了。（注意 $0$ 也可以忽略掉。）

考虑最优的选法：显然最优解选择的每一段两端都必须是正数。

再考虑一种贪心做法：只选值为正数的段。

考虑以上两种选法的区别：

• 可能从贪心做法中删除了一些原来选择的段。

• 也可能将贪心做法中原来的两个相邻但不相连的段合并了。

容易证明这两种操作的影响都是使得答案减少了删除或添加的那个段的绝对值，并且总段数变少 $1$。所以我们肯定贪心地选择对绝对值最小的段进行操作，具体算法如下：

• 每次选取绝对值最小的段，将答案减去其最小值，将该段与左右两段合并并重新加入优先队列中，在从原数列中删除左右两段。

• 必须保证每次选取的数不能已经被删除。

• 若选取到最左端或最右端的段，直接删除即可。

• 重复以上操作直到段数不超过 $m$。

// 2023.07.05

#include<bits/stdc++.h>
using namespace std;

int n,m,a[100001],pre[100001],nxt[100001];
bool vis[100001];
priority_queue<
    pair<int,int>,
    vector<pair<int,int> >,
    greater<pair<int,int> >
> Q;

void deleteinList(int x){
    vis[x]=true;
    pre[nxt[x]]=pre[x];
    nxt[pre[x]]=nxt[x];
}

int main(){
    scanf("%d%d",&n,&m);
    int tmp=0;
    for(int i=1;i<=n;i++){
        int x; scanf("%d",&x);
        if(x==0)continue;
        if(!tmp||1ll*a[tmp]*x<0)a[++tmp]=x;
        else a[tmp]+=x;
    }
    n=tmp;
    int total=0,sum=0;
    for(int i=1;i<=n;i++)
        if(a[i]>0)total++,sum+=a[i];
    for(int i=1;i<=n;i++)
        pre[i]=i-1,nxt[i]=i+1,Q.push({abs(a[i]),i});
    while(total>m){
        while(vis[Q.top().second])Q.pop();
        int x=Q.top().second; Q.pop();
        if(a[x]>0||(a[x]<0&&pre[x]!=0&&nxt[x]!=n+1)){
            total--,sum-=abs(a[x]);
            a[x]=a[pre[x]]+a[nxt[x]]+a[x];
            Q.push({abs(a[x]),x});
            deleteinList(pre[x]);
            deleteinList(nxt[x]);
        }
        else deleteinList(x);
    }
    printf("%d\n",sum);
    return 0;
}