Luogu P6631 [ZJOI2020] 序列

关于这题的暴力做法可以看ZJOI2020颓废记，此处不再赘述

我们考虑从第一个位置开始考虑，设区间所有数减(1)为第一类操作，区间奇偶数减(1)为第二类操作

考虑对于第一个位置，当它为左端点时，我们显然需要预先把它减成(0)

首先有一个显而易见的贪心：先尽可能进行第一类操作，然后在进行第二类操作直到把数变为(0)

贪心的正确在于无论何时开始一种新的操作都要付出(1)的代价，而因为此时我们考虑该点为左端点，因此优先进行第一类操作肯定不会变劣

考虑当(a_1)变为(0)之后，我们可以以类似的步骤去操作后面的数，而这样会带来一个问题，后面的数已经预进行了一些操作，我们设第一类操作数为(c_0)，第二类操作数为(c_2)

显然我们需要把(c_0,c_2)向(a_i)取(min)，表示还有多少可以传到后面

讨论(c_0+c_2)与(a_i)的关系，若(c_0+c_2<a_i)显然可以直接减去，否则（以下是这题最妙的一步）

令(k=c_0+c_2-a_i)，显然现在(c_0-k)次第一类操作和(c_2-a_i)都是必须执行的，而剩下的(k)次操作可以在第一类和第二类之间随便选，而不用付出任何代价

我们考虑给(a_i)修改成(k)，在做下一个位置的时候讨论掉(a_i)的取法，但是由于这个(k)是不占用操作次数的，因此要把(ans)减去(k)

总体复杂度(O(n))，具体实现详见代码

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,a[N],c0,c1,c2,k; long long ans;
int main()
{
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		for (ans=c0=c1=c2=0,i=2;i<=n;++i,swap(c1,c2))
		{
			c0=min(c0,a[i]); c2=min(c2,a[i]); if (c0+c2>a[i])
			k=c0+c2-a[i],c0-=k,c2-=k,a[i]=0; else k=0,a[i]-=c0+c2;
			int t=min(a[i-1],a[i]); a[i-1]-=t; a[i]-=t; ans+=t; c0+=t;
			ans+=a[i-1]; c1+=a[i-1]; if (k) ans-=k,a[i]=k;
		}
		printf("%lld
",ans+a[n]);
	}
	return 0;
}