题目背景
翰翰 18 岁生日的时候，达达给她看了一个神奇的序列 $ A_1,A_2,\dots ,A_n $ 。她被允许从中选择不超过 $ M $ 个连续的部分作为自己的生日礼物。
翰翰想要知道选择元素之和的最大值。
你能帮助她吗？
解题思路
可以先合并序列中连续的同为正或负的值，使原序列变为一个一正一负排列的序列。
先将所有正数相加存入 $ ans $ ,记录目前的段数 $ positive $ ，因为只取 $ M $ 段，我们可以尝试以下方法。
- 减去一个正数。
- 加上一个负数，并使相邻的正数连成一段。
上述两种操作均会使目前的段数 $ positive-1 $ ，直到 $ positive=M $ 时，最终的 $ ans $ 就是我们想要的结果。
而我们想要 $ ans $ 尽量大，所以减去的正数要尽量小或加上的负数要尽量大，等价于求 $ \left| A_i \right|_ {min} $ 。所以我们可以将所有数取绝对值存入小根堆，每次找堆顶操作。连成一段的操作可以用链表修改前驱和后继，使其连成一段。
注意： 若最左边和最右边的值为负的，显然是不用取的，需要特判一下。
代码
#include<cstdio>
#include<queue>
using namespace std;
typedef long long LL;
constexpr int N=1e6+10;
constexpr LL inf=1e18;
typedef pair<LL,LL> PII;
priority_queue<PII,vector<PII>,greater<PII>>q;
LL n,m,positive,maxn;
LL d[N],l[N],r[N];
bool v[N];
bool check_symbols(LL x,LL y)
{
if((x>=0&&y>=0)||(x<0&&y<0))return 1;
return 0;
}
LL abs(LL x){return x>0?x:-x;}
void remove(int x)
{
l[r[x]]=l[x];
r[l[x]]=r[x];
v[x]=true;
}
int main()
{
scanf("%lld%lld",&n,&m);
LL dlen=1;
scanf("%lld",&d[dlen]);
for(int i=2,x;i<=n;i++)
{
scanf("%lld",&x);
if(!x)continue;
if(check_symbols(d[dlen],x))
d[dlen]+=x;
else
d[++dlen]=x;
}
LL ans=0;
for(LL i=1;i<=dlen;i++)
{
l[i]=i-1;r[i]=i+1;
if(d[i]>0)ans+=d[i],positive++;
q.push({abs(d[i]),i});
}
while(positive>m)
{
PII con=q.top();
q.pop();
int x=con.second;
if(v[x])continue;
if(d[x]>0||(l[x]!=0&&r[x]!=dlen+1))
{
ans-=con.first;
d[x]+=d[l[x]]+d[r[x]];
q.push({abs(d[x]),x});
remove(r[x]);
remove(l[x]);
--positive;
}
}
printf("%lld\n",ans);
return 0;
}
还是很水的啊。我不说是谁做了一天