题目描述

[ZJOI2020] 序列

题解

题目在连续删除操作的基础上增加了跳删操作，相当于你可以用若干条直线和跳线覆盖每个点，要求每个点恰好被覆盖 a[i] 次

贪心考虑最简单的情况，只有1、2两个点：

1. a1>0,a2>0，从1向后连 min(a1,a2) 条直线；
2. a1>0,a2=0，从1向后连 a1 条跳线；
3. a1=0,a2>0，暂不处理。

这样，到第三个点时，假设连过来 z 条直线和 b 条有效的跳线，

若 z+b≤a3 那肯定直接减去 z+b；

若 z+b>a3，意味着有 z+b-a3 条线要被剪掉，那么具体剪直线还是跳线呢？很多人会卡在这里，以为肯定优先剪跳线保留直线（我一开始也这么认为），但是发现过不了大样例，具体看这个：

4 1 3 0 3 0 3

扫到第一个3时，有1条直线和3条跳线，显然保留跳线；

所以我们发现，保留直线还是跳线取决于后面的点，所以可以做个标记：设 k=z+b-a3 ，把 z 和 b 都减去 k，然后给该点 k 次免费的直线或跳线，于是在该店决策时，可以假设这 k 条线已经确定，那么 a3 刚好减为 0，再与 a2 进行两点贪心，

然后怎么处理标记，我们可以将 a3 再加上 k，然后将 ans 减去 k，因为重新加上的 k 个最后必定会被减去 k 次，即这 k 条线会被算 k 个贡献，要在答案中把它免掉；

算法在这基本上完整了，但是还有个问题：z 和 b 不能被减为负数

想想如果 z<k，即 z<z+b-ai，b>ai，只能保留 ai 条线，那么跳线必然被剪掉 b-ai 条，这时 k'=z+ai-ai=z，z 不会减为负；

b<k 同理。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<queue>
#define ll long long
#define MAXN 100005
#define mod 998244353ll
using namespace std;
inline ll read(){ll x=0,f=1;char s=getchar();while((s<'0'||s>'9')&&s>0){if(s=='-')f*=-1;s=getchar();}while(s>='0'&&s<='9'){x=(x<<1)+(x<<3)+s-'0';s=getchar();}return f>0?x:-x;
}
int T=read(),n,m,p;
ll a[MAXN];
int main()
{while(T--){n=read(),m=n+1>>1;for(int i=1;i<=n;i++)a[i]=read();ll z=0,b=0,c=0,ans=0;a[n+1]=0;for(int i=2;i<=n+1;i++){ll d=0;if(a[i]<z+b){ll k=z+b-a[i];if(k>z)b-=k-z,k=z;if(k>b)z-=k-b,k=b;z-=k,b-=k,a[i]-=k,d=k;}a[i]-=z+b;ll mn=min(a[i],a[i-1]);a[i-1]-=mn,a[i]-=mn,ans+=mn,z+=mn;ans+=a[i-1],c+=a[i-1],a[i-1]=0;a[i]+=d,ans-=d,swap(b,c);}printf("%lld\n",ans);}return 0;
}