题解：P6631 [ZJOI2020] 序列

· · 题解

对 这篇题解 进行一个解释说明。而且其实我也有不会证明的部分。

我们称一操作是直线操作，二三操作时跳线操作。

首先想到贪心。考虑做一些操作把 a_1 变成 0 再递归处理。此时我们能发现，若 a_1>0 且 a_2>0 ，那么一定有一个过 1 的直线操作。

证明：若不存在则意味着 a_1 会做一次跳线操作，a_2 会做一次跳线操作，可以把这两次操作合并，效果不变。

那么比较好的想法是，先做一些操作把 \min(a_1,a_2) 变成 0，然后若 a_1>0，再补充一些跳线操作。

但是我们要考虑递归时会有一些之前的操作传过来。假设我们枚举到 i，设 i-2 及以后都是 0，我们要把 a_{i-1} 变成 0。此时有 A 个 i-1\to i 的直线操作，B 个 i-2\to i 的跳线操作，C 个 i-1\to i+1 的跳线操作。

由于若已经处理了前面操作对 a_i 的影响后就可以按照上述做法直接做了，所以我们只考虑前面对 a_i 的影响。

若 a_i\leq A+B，那么我们贪心的把所有跳线和直线都保留，a_i\gets a_i-A-B。

若 a_i>A+B，我们还是贪心的把 a_i\gets 0，但是保留直线操作还是跳线操作呢？

设 K=A+B-a_i，表示我们要删掉 K 个直线或跳线操作。若 K>A，意味着至少要删 K-A 个跳线，那么直接删，K>B 同理。所以我们钦定 A,B\geq K。

我们注意到，直线和跳线不重要，重要的是他们都是从 i 开始的，我们不妨认为直线和跳线都删了 K 个，最后再反悔 K 次操作，怎么反悔呢？我们 a_i\gets K，那么当 i\gets i+1 的时候，我就必须要选择恰好 K 次操作把 a_i 干掉，并且我们不关心反悔的是直线还是跳线。

于是这个问题就可以递归处理了！时间复杂度 O(n)。

但其实我仍然有不懂的地方：

1.为什么直接贪心没有后效性；

2.为什么让 a_i 尽可能的小会更优。

我只能感性理解，但是能想到这个贪心还是很厉害的。

可以根据代码理解贪心流程。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n,a[N];
void work(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    a[n+1]=0;
    LL A=0,B=0,C=0,ans=0;
    for(int i=2;i<=n+1;i++){
        LL tag=0;
        if(a[i]<A+B){
            LL K=A+B-a[i];
            if(K>B) A-=K-B,K=B;
            if(K>A) B-=K-A,K=A;
            a[i]=0;
            A-=K,B-=K,tag=K;
        }else a[i]-=A+B;
        LL Min=min(a[i-1],a[i]);
        a[i]-=Min,a[i-1]-=Min,ans+=Min,A+=Min;
        C+=a[i-1],ans+=a[i-1],a[i-1]-=a[i-1];
        a[i]+=tag,ans-=tag;
        swap(B,C);
    }
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    // freopen("b.in","r",stdin);
    // freopen("b.out","w",stdout);
    int T=1;
    cin>>T;
    while(T--){
        work();
    }
    cerr<<1.0*clock()/CLOCKS_PER_SEC<<'\n';
    return 0;
}