题目简述：
给你n个数，让你选取不超过m个连续的区间，区间不重叠，求区间总和最大。
标准输入
5 2
2 -3 2 -1 2
标准输出
5
思路：
1.很显然能够想到把原数组简化成形如一正一负的数组。
2.特殊情况，当正数连续块小于等于m时答案很显然是所有正数相加。
3.一般情况，当正数连续块大于m时，先统计所有正数的总和，再考虑合并区间。这时候，只剩下两种可以选择的操作，选择一个正数，让其左右两侧负数合并；选择一个负数，让其左右两侧的正数合并。很容易发现在这之后这左右两侧的数无法再被选中。
先来说说选择正数，合并负数的情况，这时候相当于舍弃了这个正数，正数连续块-1。
再来看看选择负数，合并正数的情况，这时候相当于吸纳了这个负数，使两个正数连续块合并了，正数连续块-1。
那么直至正数连续块=m时，此时所有的正数连续块总和就是答案。
所以很容易想到贪心的做法，看看舍弃正数的代价小还是吸纳负数的代价小。
比较特殊的情况，当负数在数组两侧时，选择该负数不会产生任何效果。
#include<bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define int long long typedef unsigned long long llu; const double e=1e-7; const int N=1e5+7; const int MOD=1e9+7; const int LINF=1e18; const int P=131; bool C=0; int a[N]; int le[N],ri[N]; void move(int x){ a[x]=LINF; le[ri[x]]=le[x]; ri[le[x]]=ri[x]; } void solve(){ int n,m; cin>>n>>m; int I=0; for(int i=1;i<=n;i++){ //把给定的数组变成 正负正负的数组，处理0是关键 int x; cin>>x; if(x==0) continue; if(a[I]*x>0) a[I]+=x; else a[++I]=x; } int res=0; int sum=0; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q; for(int i=1;i<=I;i++){ if(a[i]>0) res+=a[i],sum++; le[i]=i-1; ri[i]=i+1; q.push({abs(a[i]),i}); } if(m>=sum){ //若整数连续块小于等于m则直接输出即可 cout<<res<<endl; return; } while(true){ if(sum<=m) break; //退出条件 if(q.top().first!=abs(a[q.top().second])){ //清除无用的状态 q.pop(); continue; } int x=q.top().second; q.pop(); if(a[x]<=0&&(le[x]==0||ri[x]==I+1)){ //如果边界是负数则不产生影响 if(le[x]==0) le[ri[x]]=le[x]; if(ri[x]==I+1) ri[le[x]]=ri[x]; a[x]=LINF; continue; } else{ res-=abs(a[x]); a[x]+=a[le[x]]+a[ri[x]]; /* 可以思考一下，下列代码能否替换move函数 a[le[x]]=LINF; a[ri[x]]=LINF; ri[le[le[x]]]=x; le[x]=le[le[x]]; le[ri[ri[x]]]=x; ri[x]=ri[ri[x]]; */ move(le[x]); move(ri[x]); sum--; } q.push({abs(a[x]),x}); } cout<<res<<endl; } signed main(){ IOS; int t; if(C) cin>>t; else t=1; while(t--) solve(); }