BZOJ 生日礼物

题目背景

翰翰 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;
}

还是很水的啊。我不说是谁做了一天