最大M子段和

未分类

题目链接：http://www.51nod.com/Challenge/Problem.html#!#problemId=1053

长度为$n$的整数数列$\{ a_i \}$，最多取$m$个不相交子段求和，问和最大是多少？

先把数列中所有$0$去掉，然后把相邻的同号的加起来，这时数列的相邻两个数肯定不同号。对于处理后的数组，把所有正数加到$ans$里，设正数的个数有$x$个，如果$M \ge x$，那么答案就是$ans$，如果$M<x$，设$k=M-x$。

每次取出数列中绝对值最小的数$a_i$，如果是负数，则视为将其左右两块正数合并，代价是$ans -= |a_i|$；如果是正数，则视为将这块舍掉，然后和左右两块负数合并，代价也是$ans-=|a_i|$。重复进行$k$次。

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdlib>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<ll,int>pii;
const int N=1e5+10;
ll a[N];
int l[N],r[N];
struct Node{
    ll val;
    int id;
    Node(){}
    Node(ll val,int id):val(val),id(id){}
    bool operator < (const Node& tmp)const{
        return pii(abs(val),id)<pii(abs(tmp.val),tmp.id);
    }
};
void del(int i){
    l[r[i]]=l[i];
    r[l[i]]=r[i];
}
const int BS = 1e7;
char buf[BS];
char *head,*tail;
int flag=0;
char getch(){
    if(head==tail){
        int len = fread(buf,1,BS,stdin);
        tail = (head = buf)+len;    
        flag++;
        if(flag>=2) exit(0);
    }
    return *head++;
}
template<typename T>
void scan(T& x){
    x=0;
    char ch=getch();
    while(!(ch=='-' || (ch>='0' && ch<='9'))) ch=getch();
    bool flag=0;
    if(ch=='-') flag=1,ch=getch();
    while(ch>='0' && ch<='9') x=10*x+ch-'0',ch=getch();
    if(flag) x=-x;
}
void solve(){
    int n,tot;
    scan(n),scan(tot);
    for(int i=1;i<=n;i++) scan(a[i]);
    int m=0;
    for(int i=1;i<=n;i++) if(a[i]!=0) a[++m]=a[i];
    n=m,m=0;
    for(int i=1;i<=n;){
        int j=i;
        while(j+1<=n && 1LL*a[j+1]*a[j]>0) j++;
        ll tmp=0;
        for(int k=i;k<=j;k++) tmp+=a[k];
        i=j+1,a[++m]=tmp;
    }
    n=m;
    for(int i=0;i<=n;i++) r[i]=i+1;
    for(int i=1;i<=n+1;i++) l[i]=i-1;
    set<Node>st;
    for(int i=1;i<=n;i++){
        st.insert(Node(a[i],i));
        if(a[i]>0) tot--;
    }
    ll ans=0;
    for(int i=1;i<=n;i++) if(a[i]>0) ans+=a[i];
    tot=-tot;
    while(tot>0){
        Node u = *st.begin();
        st.erase(u);
        if(u.val==0) continue;
        if(u.val<0){
            if(l[u.id]==0 || r[u.id]>n) continue;
            ans-=abs(u.val);
            ll tval=u.val + a[l[u.id]] + a[r[u.id]];
            a[u.id]=tval;
            st.erase(Node(a[l[u.id]],l[u.id]));
            st.erase(Node(a[r[u.id]],r[u.id]));
            del(l[u.id]);
            del(r[u.id]);
            st.insert(Node(a[u.id],u.id));
        }
        else{
            ans-=abs(u.val);
            ll tval=u.val;
            if(l[u.id]!=0){
                tval += a[l[u.id]];
                st.erase(Node(a[l[u.id]],l[u.id]));
                del(l[u.id]);
            }
            if(r[u.id]<=n){
                tval += a[r[u.id]];
                st.erase(Node(a[r[u.id]],r[u.id]));
                del(r[u.id]);
            }
            a[u.id]=tval;
            st.insert(Node(a[u.id],u.id));
        }
        tot--;
    }
    cout<<ans<<endl;
}
int main(){
    while(1) solve();
    return 0;
}