题目描述
blablabla
样例
blablabla
算法1
膜拜大佬题解
若数据备份不太懂的同学,推荐看一下我这篇打卡
我们曾经做过一道题数据备份,与这个非常类似,只不过那道题是a[i]>=0,求最小值.
而这道题是:给出n个线段,从中任意选出<m段连续的区间(相不相邻无所谓,因为我们不用特意分开,只需<m就可以了,而且如果特意分成两个，对答案也没有影响),要求总和最大。
所以我们要想办法把这道问题转换为数据备份。
首先,我们知道,零不用考虑,因为没有什么影响,仅有的链接两个不为零的两个数使他们能在同一个连续序列里,删掉后反而相邻了 -_-
接着,我们考虑到全选正数在条件满足的情况下一定是最优的。
所以我们先把他们全选上如果段数<=m,直接输出.
但若>m,我们就须考虑减小一些段数了。
而且我们知道一个性质,相邻的正数或负数必须全部选。
why?若<m,你在一段连续的区间(全是正)内少选了一个正数。那么你选上这个正数一定比刚刚的策略好。
若>m,你在连续的区间里少删了一个正数,那么总段数还是没有减小。而你把他删掉不就是为了让总段数减少吗?，你留着他作甚。
若是负数,我们选负数的目标是链接两个相邻的正数。所以单选没有意义。而链接时你要么全选,要么全不选,若只选了一半,总段数还是没变,你那他作甚。
那么我们就可以把连续的正数和负数所称一个点来考虑。
则我们可以得到一个性质。正数段和负数段交错相间(毕竟都是正数的或负数的已经被缩成一个点了)
我们再思考如何删掉总段数。
我们知道,有且仅有以下两种策略可以减小总段数。我们设
全选的正数和为ans,选的段数为num
1.去掉一个正数段,ans-=这个正数段,num–.
2.链接相邻两个正数段,这个段是负数段,ans-=abs(这个负数段),num–
我们发现每次ans都要减去这个段的绝对值,于是入队时直接入绝对值就可以了。
而我们发现,如此,就转化成了上面的问题.虽然没有要求相邻不相邻,但我们这个做法可以转化为不相邻。
具体来说,对于每个数,若他是正数(标号设为i,值为a[i]),那么他可以删他自己,但他两边的数不能删(因为他两边都是负数,都连了个寂寞),这样子肯定不优
若他取两边的负数,那么他自己就不能删,否则负数还是连了个寂寞，不优
负数也同理,只不过上面两端的取变成了删,删变成了取,可以自己替换看看。
根据上面,我们知道,这道题的约束条件是贪心策略,而不是题目条件的约束。所以我么要学会转化~
你细品,越想越妙~
时间复杂度
O(n)
参考文献
C++ 代码
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define int long long
using namespace std;
const int N=1e5+1e3;
int a[N];
int pre[N],nxt[N];
int n,m;
bool v[N];
int tot,num,ans;
priority_queue<pii,vector<pii>,greater<pii> >q;
void work(int x)
{
pre[nxt[x]]=pre[x];
nxt[pre[x]]=nxt[x];
v[x]=0;
}
signed main()
{
memset(v,1,sizeof(v));
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
{
int x;scanf("%lld",&x);
if(x==0)continue;
if(!tot||a[tot]*x<0)a[++tot]+=x;
else a[tot]+=x;
//并成一段
}
for(int i=1;i<=tot;i++)
{
pre[i]=i-1;nxt[i]=i+1;
q.push(mp(abs(a[i]),i));
if(a[i]>0)ans+=a[i],num++;
//加上正数
}
// cout<<ans<<' '<<num<<endl;
while(num>m)
{
pii x=q.top();q.pop();
if(!v[x.se])continue;
if(a[x.se]>0||(pre[x.se]!=0&&nxt[x.se]!=tot+1))
//若是负数,得确保两边都有正数,否则连了个寂寞.不优
{
ans-=x.fi;
a[x.se]+=a[pre[x.se]]+a[nxt[x.se]];
q.push(mp(abs(a[x.se]),x.se));
work(pre[x.se]);work(nxt[x.se]);
num--;
}
}
printf("%lld\n",ans);
}
/*
*/
