题意
描述
ftiasch 18岁生日的时候，lqp18_31给她看了一个神奇的序列 A1, A2, ..., AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。ftiasch想要知道选择元素之和的最大值。你能帮助她吗？
输入格式
第一行两个整数N,M。
第二行N个整数A1~AN。
输出格式
一个整数，表示答案。
样例输入
5 2
2 -3 2 -1 2
样例输出
5
数据范围与约定
对于100%的数据: N,M<=10^5, |Ai|<=10^4
来源
北京大学
分析
参照solider98的题解。
设输入序列为A[1...n], 将A的首尾的连续的非正数去除的序列B[1...m], 将序列B所有相邻的正数合并, 所有相邻的非正数合并.得到序列C[1...p], C[1...p]为正, 非正交替的序列且C[1] > 0, C[p] > 0, C[1...p]中正数的个数大于M, 设C[i]为C[1...p]中绝对值最小的数, 那么有如下结论成立:
结论1: 如果i = 1或i = p那么一定存在不包含C[i]和与C[i]相邻的元素的最优选择方案(所选则的至多M个连续的部分的和最大的选择方案, 根据C[i]的绝对值最小, 且与C[i]相邻的元素必为绝对值不小于C[i]的负数较易证明此结论)
结论2: 如果1 < i < p, 那么存在最优的选择方案同时包含C[i - 1], C[i], C[i + 1]
证明:
(1)当C[i] > 0时, 假设存在最优方案R只包含三者中的一个, 显然不可能只包含Ci - 1或Ci + 1, 即只包含C[i], 由于C中正数的个数大于M, 故可使用任意未被选择的整数C[j]替换C[i], 替换之后所有选择的数的和不会减小.假设存在最优方案R只包含三者中的两个, 显然不能为C[i - 1]和C[i + 1], 不妨设包含C[i]和C[i + 1], 此时去掉C[i]和C[i + 1]剩余选择的元素之和不会减小. 故C[i] > 0时, 存在最优方案同时包含C[i - 1], C[i]和C[i + 1]或同时不包含.
(2)当C[i] <= 0时, 假设存在最优方案R只包含三者中的一个, 显然不可能只包含C[i], 不妨设包含C[i - 1], 此时将C[i]和C[i - 1]包含进来, 同时选择的元素之和不会减小, 假设最优方案R只包含三者中的两个, 显然不可能包含C[i - 1]和C[i]或C[i + 1]和C[i], 即只能包含C[i - 1]和C[i + 1], 此时可包含进C[i]使得选择的连续的部分个数减少1, 因此可在C中选择任意一个之前R中未被选择的正数, 且所选择的元素之和不会减小, 故C[i] <= 0时, 存在最优方案同时包含C[i - 1], C[i]和C[i + 1]或同时不包含.
基于结论2, 可不断减少序列中正数的个数, 直至正数的个数不超过M(此时最优方案选择所有的正数)
时间复杂度(O(N log N))
代码
#include<bits/stdc++.h>
#define co const
#define il inline
#define rg register
#define fi first
#define se second
#define mp make_pair
template<class T>il T read(){
rg T data=0,w=1;
rg char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') w=-1;
ch=getchar();
}
while(isdigit(ch))
data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x){
return x=read<T>();
}
typedef long long LL;
using namespace std;
co int MAX=1e5+5;
int A[MAX],N,M;
pair<int,int> he[MAX];int size;
pair<int,int> li[MAX<<1];int head,tot,nex[MAX<<1],pre[MAX<<1];
bool cmp(int a,int b){
return abs(he[a].fi)<abs(he[b].fi);
}
void hswap(int a,int b){
swap(li[he[a].se].se,li[he[b].se].se),swap(he[a],he[b]);
}
void up(int a){
for(int q=a,p=q>>1;p&&cmp(q,p);hswap(q,p),q=p,p=q>>1);
}
void down(int a){
for(int p=a,l=p<<1,r=l+1,t;
l<=size&&(cmp(l,p)||r<=size&&cmp(r,p));
t=r>size||min(l,r,cmp)==l?l:r,hswap(p,t),p=t,l=p<<1,r=l+1);
}
void hins(pair<int,int> pa){
he[++size]=pa,up(size);
}
void hdel(int a){
hswap(a,size--);if(a!=size+1) up(a),down(a);
}
void lins(int a,pair<int,int> b){
li[++tot]=b;
if(!a) nex[tot]=head,pre[head]=tot,head=tot;
else nex[tot]=nex[a],pre[tot]=a,pre[nex[a]]=tot,nex[a]=tot;
}
void ldel(int a){
if(a==head) head=nex[head],pre[head]=0;
else nex[pre[a]]=nex[a],pre[nex[a]]=pre[a];
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(N),read(M);
for(int i=1;i<=N;++i) read(A[i]);
int be=1,end=N;
while(be<=end&&A[be]<=0) ++be; while(end>=be&&A[end]<=0) --end;
if(be>end){
puts("0"); return 0;
}
A[1]=A[be];int len=1;
for(int i=be+1;i<=end;++i)
if(A[i-1]>0&&A[i]>0||A[i-1]<=0&&A[i]<=0) A[len]+=A[i];
else A[++len]=A[i];
for(int i=1;i<=len;++i)
li[i].fi=A[i],nex[i]=i+1,pre[i]=i-1;
nex[len]=0,pre[1]=0,head=1,tot=len;
for(int i=1;i<=len;++i) li[i].se=size+1,hins(mp(li[i].fi,i));
while(size/2+1>M){
int u=he[1].fi,v=he[1].se;
if(!pre[v]) hdel(li[nex[v]].se),hdel(1),ldel(nex[v]),ldel(v);
else if(!nex[v]) hdel(li[pre[v]].se),hdel(1),ldel(pre[v]),ldel(v);
else{
int t=u+li[pre[v]].fi+li[nex[v]].fi,pp=pre[pre[v]];
hdel(li[pre[v]].se),hdel(li[nex[v]].se),hdel(1),
ldel(pre[v]),ldel(nex[v]),ldel(v),
lins(pp,mp(t,size+1)),hins(mp(t,tot));
}
}
int ans=0;
for(int i=head;i;i=nex[i]) if(li[i].fi>0) ans+=li[i].fi;
printf("%d
",ans);
return 0;
}