题解：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

尽可能的小会更优。

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

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

CPP

#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;
}

题解：P6631 [ZJOI2020] 序列

文章操作

相关推荐

评论

题解：P6631 [ZJOI2020] 序列