难度：困难
主要算法：贪心
题目链接：https://www.luogu.com.cn/problem/P6631
解题思路
- 简化问题：定义直线为覆盖ai,ai+1,ai+2 的操作，跳线为覆盖ai,ai+2,ai+4的操作。题意简化为使用一些直线和一些跳线使每个位置被覆盖正好ai次。
- 小范围思考：考虑只覆盖前2个点怎么办？如果a1等于0则不管向后移动直到a不为0。当a1不为0时，取a1和a2的最小值，做最小值条直线覆盖a1和a2。再以以较大的点为起点做最大值减最小值条跳边。这样处理后，a2和a1一定为0，则我们可以跳过a1。考虑处理a2和a3，情况与上面类似，唯一的不同是要对a3处理前面的边覆盖带来的影响。对a3有影响的是直线和与a奇偶性相同的跳线。设A为直线，B为奇偶性相同的跳线，则a3被覆盖了A+B次。有二种情况，一是a3大于A+B，则用a3-=A+B，二是a3小于A+B，情况更复杂了。我们再设一个K等于A+B-a3,将A-=k,b-=K,但要一定要保证A和B为正，然后我们应该在a3的位置上做一个标记，表示在a3的位置，向后可以免费延伸出K条线，这些线可以是直线或跳线。最后按a和a的情况处理。
- 算法设计：由上文可知，我们可以递推处理答案。
#include <bits/stdc++.h> using namespace std; int t,n,a[100010]; long long A,B,C,D,ans,bi; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); A=0,B=0,C=0,D=0,ans=0;//A是直线，B是与i奇偶性相同的跳线，C是另一类跳线，D是记录可以免费提供的线 for(int i=2;i<=n+1;i++) { if(a[i]<A+B)//如果前面的覆盖数大于需要 { int K=A+B-a[i]; if(K>B)A-=K-B,K-=K-B; if(K>A)B-=K-A,K-=K-A;//保持A,B>=0; A-=K,B-=K,a[i]-=K,D=K;//将K记录下来 } a[i]-=A+B;//减去前面的覆盖数 bi=min(a[i-1],a[i]);//取最小值 ans+=bi,a[i-1]-=bi,a[i]-=bi,A+=bi;//用最小值更新答案 ans+=a[i-1];C+=a[i-1];a[i-1]=0;//彻底处理掉ai-1的值 a[i]+=D;ans-=D;D=0;//ai回归正常值，K条边不用价值，标记清零 swap(B,C);//奇偶交换 } printf("%lld\n",ans); } return 0; }