CF2031D Penchick and Desert Rabbit 题解

CF2031D Penchick and Desert Rabbit

赛时 A,B,C 共计吃了 5 发罚时，这就是我的真实实力！来补篇题解。

考虑分析每一个位置的性质，不难发现最后一个位置一定能跳到最大值的位置。

接下来，我们考虑第 n-1 个位置。类比最后一个位置，我们发现，这个位置一定能跳到 1\sim n-1 内含有的最大值。此时，1\sim n-1 内的其他树均没有意义。因为一方面它们不会成为答案，一定不会被跳到，另一方面由于往后跳只能跳到更小的位置，所以若要跳到 n，则选取 1\sim n-1 内的最大值就够了。如果可以跳到，我们发现可以直接跳到最后一个位置能跳到最大值，可以直接继承。

我们不妨推广一下。如果已知 i+1 能跳到最大值，如何求出 i 能跳到最大值？显然还是一定能跳到 1\sim i 内含有的最大值，且必然还是从最大值往回后跳。考虑往后跳能跳到的最大位置一定是 i+1 能跳到最大值，如果不是 i+1 能跳到最大值，那么 i+1 一定也能跳到这个位置，矛盾。因此，我们只需要看能不能跳到 i+1\sim n 的最小值，再直接跳到 i+1 继承能跳到最大值即可。

这样一想，动态规划的思路就清晰了。预处理前缀最大值与后缀最小值，即可做到 O(n) 递推。

#include <bits/stdc++.h>
using namespace std;
long long t,n,a[600000],mx[600000],mi[600000],f[600000];
int main()
{
    scanf("%lld",&t);
    while(t--)
       {
        scanf("%lld",&n);
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        mx[0]=0,mi[n+1]=1e18;
        for(int i=1;i<=n;i++)mx[i]=max(mx[i-1],a[i]);
        for(int i=n;i>=1;i--)mi[i]=min(mi[i+1],a[i]);
        f[n]=mx[n];
        for(int i=n-1;i>=1;i--)
            if(mx[i]>mi[i+1])f[i]=f[i+1];
            else f[i]=mx[i];
        for(int i=1;i<=n;i++)printf("%lld ",f[i]);
        printf("\n");
       }
    return 0;
}