BZOJ2288 生日礼物

题意

在长度为 $N$ 的数列中选择不超过 $M$ 段连续的数，求这些数总和的最大值。

$N,M\le 10000$ 。

题解

可以先将连续的相同符号的数合并起来，并忽略 $0$ 。因为取正数时一定会把一整段取完，取负数也肯定会把自己这段和两边的正数段取完。

这样得到的新序列是正负交替的，下面处理新数列。

先贪心的把所有正数取完，并记正数的个数为 $cnt$ 。如果 $cnt\le m$ ，那么此时就已经得到答案；否则需要进行调整，方式有两种：

1. 不取某个正数
2. 将两个正数合为一段，此时需要取中间的负数。

将所有数的绝对值放入一个优先队列，每次取最小的从答案中扣除。如果选择的是正数，就相当于不取；如果是负数，就相当于取了这个负数，并把左右两个数合为一段。

其它的就和 数据备份 差不多了。用数组模拟链表进行合并即可。

但还是有区别，对于两端的数，如果是负数则不能取，因为没有两个正数能合为一段。

还需要注意合并同符号的数时，因为可能有 $0$ ，所以相乘判断符号时应该用当前的新数列而不是旧数列的上一项（见代码）

#include<bits/stdc++.h>
#define pr pair<int,int>
#define mp make_pair

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

bool vis[100005];
priority_queue <pr,vector<pr>,greater<pr> > q;
int n,m,a[100005],s[100005],l[100005],r[100005];

inline void del(int x) //删除节点
{
    vis[x]=1;
    l[r[x]]=l[x];
    r[l[x]]=r[x];
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) a[i]=read();
    int cnt=0;
    s[++cnt]=a[1];
    for (int i=2;i<=n;i++)
    {
        if (!a[i]) continue;
        if (a[i]*s[cnt]>0) s[cnt]+=a[i]; //不能用 a[i]*a[i-1] 因为可能 a[i-1]=0
        else s[++cnt]=a[i];
    }
    n=cnt;
    int ans=0; cnt=0;
    for (int i=1;i<=n;i++)
    {
        if (s[i]>0) ans+=s[i],cnt++; //贪心取正数
        l[i]=i-1; r[i]=i+1;
        q.push(mp(abs(s[i]),i));
    }
    if (cnt<=m) return !printf("%d",ans);
    m=cnt-m; //需要操作的次数 
    while (m)
    {
        while (vis[q.top().second]) q.pop();
        int x=q.top().first,y=q.top().second; q.pop();
        if ((!l[y] || r[y]==n+1) && s[y]<0) { del(y); continue; } //两端且 <0 则跳过
        m--;
        ans-=x;
        s[y]+=s[l[y]]+s[r[y]]; //将左右两段合并
        q.emplace(mp(abs(s[y]),y));
        del(l[y]); del(r[y]);
    }
    return !printf("%d",ans);
}