神贪 QAQ
题目链接
Solution
我们定义从 (i) 出发的一类操作为 (i,i+1,i+2,dots) 加一，二类操作为 (i,i+2,dots) 加一。
先说一个结论：
若 (a_1>0,a_2>0)，则存在一种最优方案，至少有一次从 (1) 出发的一类操作。
证明：
考虑反证，分两种情况。
（1）从 (1) 出发了一个二类操作，(2) 出发了一个一类操作：
这时可以把 (1) 移出这个二类的操作范围，加入后面的一类操作，这样就形成了一个从 (1) 出发的一类操作和一个从 (3) 出发的二类操作，答案一定不会更劣。
（2）从 (1) 出发了一个二类操作，(2) 出发了一个二类操作：
设两次操作分别影响了 (x) 和 (y) 个位置，则取 (t=min(x,y))，把两次操作影响的前 (t) 个位置并成一个长度为 (2t) 的一类操作，剩下的 (max(x,y)-t) 个位置必然会被一次二类操作覆盖，答案也不会更劣。
于是有一个贪心：设 (t=min(a_1,a_2))，先从 (1) 出发 (t) 次一类操作（长度至少为 (2)），再从 (1) 出发 (a_1-t) 次二类操作。这样之后 (a_1=0)，可以把 (a_1) 删掉之后继续考虑下一个数。
这样存在一个问题：上面的过程只影响了 (a_1,a_2) 两个数，对后面的数的影响无法快速处理。
故记录三个标记 (A,B,C) 表示可以当前免费从 (i+1) 出发 (A) 个一类操作和 (B) 个二类操作，从 (i+2) 出发 (C) 个二类操作。
然后 (i) 从 (1) 到 (n)，如果从 (a_i) 出发了 (t) 次一类操作，则只需将 (a_i) 和 (a_{i+1}) 都减掉 (t) 之后把 (A) 加上 (t)，如果从 (a_i) 出发 (s) 次二类操作，则把 (a_i) 减掉 (s)，(C) 加上 (s)，之后让 (i) 加一并 swap 一下 (B) 和 (C)。
那么现在的主要问题就是处理之前的 (A,B) 标记对 (i+1) 的影响。如果 (A+Ble a_{i+1}) 则直接把 (a_{i+1}) 减掉 (A+B) 即可。
否则 (a_{i+1}) 减为 (0)，但在这之前需要确定 (x+y=a_{i+1},xle A,yle B)，从 (i+1) 出发 (x) 次一类操作和 (y) 次二类操作。(x) 和 (y) 的具体值和后面的数有关。
设 (K=A+B-a_{i+1})，把 (A) 和 (B) 分别减掉 (K)，表示可以从 (i+1) 免费出发 (K) 次任意的操作。
这样有另一个问题：(A) 和 (B) 会被减成负数。
考虑如果 (A<K)，则在 (B) 次二类操作中一定至少有 (K-A) 次没有加在 (i+1) 上面。故可以把 (B) 减掉 (K-A)，然后把 (K) 设为 (A)。(B<K) 同理。这样之后就能保证 (Age K,Bge K) 了。
这样处理之后就可以和之前一样，进行 (min(a_i,a_{i+1})) 次一类操作和 (max(a_i-a_{i+1},0)) 次二类操作了。
由于存在任意的（可以为一类或二类）从 (i+1) 出发的 (K) 次操作，故执行完之前的操作之后要把 (a_{i+1}) 重新加上 (K)。又由于这 (K) 次操作免费，故这时要让答案减掉 (K)。
(O(n))。
Code
#include <bits/stdc++.h>
template <class T>
inline void read(T &res)
{
res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
if (bo) res = ~res + 1;
}
typedef long long ll;
const int N = 1e5 + 5;
int n, a[N];
void work()
{
ll ans = 0, A = 0, B = 0, C = 0; read(n);
for (int i = 1; i <= n; i++) read(a[i]); a[n + 1] = 0;
for (int i = 1; i <= n; i++, std::swap(B, C))
{
ll k = 0;
if (A + B > a[i + 1])
{
k = A + B - a[i + 1];
if (k > A) B -= k - A, k = A;
if (k > B) A -= k - B, k = B;
A -= k; B -= k;
}
a[i + 1] -= A + B + k; ll cnt1 = 0, cnt2 = 0;
if (a[i] < a[i + 1]) cnt1 = a[i];
else cnt1 = a[i + 1], cnt2 = a[i] - a[i + 1];
a[i] -= cnt1; a[i + 1] -= cnt1; A += cnt1; a[i] -= cnt2; C += cnt2;
ans += cnt1 + cnt2 - k; a[i + 1] += k;
}
printf("%lld
", ans);
}
int main()
{
int T; read(T);
while (T--) work();
return 0;
}