CF1407D Discrete Centrifugal Jumps

CF1407D Discrete Centrifugal JumpsTJ

蒟蒻的尸路：

考场上看到这题果断DP（这是我第一次在考场自己想DP），然后 $ O ( N ^ 3 ) $原地爆炸。

改成了 $ O ( N ^ 2 ) $ 还是炸，想到可以优化的时候……就没时间了……

我太蒻了……

DP的蜕变：

因为跳跃的步骤不影响后面的答案，不难想到一个线性DP直接莽上去：$ dp_i = \min (dp_j) + 1 $，其中 $ j $ 满足题目中的限制。

然后 $ O ( N ^ 3 ) $ 的时间复杂度直接炸开……

这也不去说什么小优化了，因为不难发现可以直接整到 $ O ( N ) $。

以第二个条件举例，手模一下后就会发现，若要更新 $ i $，那么当一个 $ j $ 出现并不满足 $ h_j < h_i $ 时，$ j $ 前面的都不可能成为候选项（因为包含 $ j $ 的都不满足要求），因此，我们可以直接排除它们。

想一下，这像什么？单调栈的板子题！

具体地，我们可以直接采用两个单调栈维护条件 2 和条件 3 的决策集合并进行转移，达到 $ O ( N ) $ 的时间复杂度，轻松 AC 本题。

这里提一嘴单调栈，是指用栈维护一个决策集合，利用单调性不停地排除无效选项（如本题删去了不合法的选项），降低总的时间复杂度。由于每个元素至多进出栈各一次，所以可以做到线性复杂度。

代码的实现：

给出伪代码（我不会写伪代码，我猜是这样）：

    dp[1]=0;
    s1.push(1),s2.push(1);//边界与初始化
    for(int i=2;i<=n;i++){
        dp[i]=dp[i-1]+1;//条件1
        while(s1的栈顶不满足){
            取出栈顶并出栈
            if(可以用来更新答案) 用栈顶更新答案
        }
        s2同上
        i入栈
    }

代码就不放了，思维最重要