定义$C_{i}$表示令$i,i+1,i+2,...$的位置减1的操作，定义$I_{i}$表示令$i,i+2,i+4,...$的位置减1的操作
结论1：一定存在一种最优解使得$forall i$不同时存在$I_{i}$和$I/C_{i+1}$操作（用其他操作等效替代即可证明）
结论2：当$a_{1},a_{2}>0$时，一定存在一种最优解使得其中一次执行了一次$C_{1}$操作（结论1的简单推论）
根据上述结论进行贪心，记录$(a,b,c)$表示可以免费进行$a$次$C_{i}$操作、$b$次$I_{i}$操作和$c$次$I_{i+1}$操作
对于每一个位置，优先使用免费操作，按以下方式选择免费操作：
1.若$a+ble a_{i}$，将这$a+b$次操作全部执行
2.若$a+b>a_{i}$，相当于要确定$x+y=a_{i}$，其中$0le xle a$且$0le yle b$
观察到$a_{i}-ble xle a$且$a_{i}-ale yle b$，那么必然要执行$a_{i}-b$次$C_{i}$操作和$a_{i}-a$次$I_{i}$操作
（这里有一个小问题：为了让次数为非负数，需要让$a$和$b$对$a_{i}$取min，这样显然不影响答案）
对于剩下的免费操作，这些免费操作的意义就是让答案减小$a_{i}'$，因此直接令答案减小$a_{i}'$即可
（之前不能这么做是因为操作有上限，而现在$a_{i}'$已经规定了上限，次数上限无意义）
考虑当处理完$a_{i-1}$和$a_{i}$的免费操作后即可贪心：执行$min(a_{i-1},a_{i})$次$C_{i-1}$操作和$max(a_{i-1}-a_{i},0)$次$I_{i-1}$操作
（还有一个细节问题：如果$a+b>a_{i}$，这$a_{i}'$次操作实际上是免费的，因此优先，所以此时$a_{i-1}$只能使用$I_{i-1}$的操作）
View Code
1 #include<bits/stdc++.h> 2 using namespace std; 3 int t,n,s1,s2,s3,a[100005]; 4 long long ans; 5 void calc1(int k,int x){ 6 a[k]-=x; 7 a[k+1]-=x; 8 s1+=x; 9 } 10 void calc2(int k,int x){ 11 a[k]-=x; 12 s3+=x; 13 } 14 int main(){ 15 scanf("%d",&t); 16 while (t--){ 17 scanf("%d",&n); 18 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 19 s1=s2=s3=ans=0; 20 for(int i=1;i<=n;i++){ 21 s1=min(s1,a[i]); 22 s2=min(s2,a[i]); 23 int k=max(s1+s2-a[i],0); 24 s1-=k; 25 s2-=k; 26 ans-=k; 27 a[i]-=s1+s2+k; 28 ans+=a[i-1]; 29 calc1(i-1,min(a[i-1],a[i])); 30 calc2(i-1,max(a[i-1]-a[i],0)); 31 swap(s2,s3); 32 a[i]+=k; 33 } 34 printf("%lld ",ans+a[n]); 35 } 36 }