[ABC336D] Pyramid 分析

__ryp__ · 2024-01-20 17:17:06 · 个人记录

赛后诸葛亮系列。思路还是不够开。

赛时写了一堆模拟，最后发现越来越复杂。事实证明，ABC 从来没有复杂的模拟题，只有你想不到的思维题。

实际上用 DP 很自然就能做出来。f(i) 为到前 i 个元素正着的最高点，g(i) 为反过来。我们要找的是正反的交汇点，也就是 \min \{f(i), g(i)\}。

然后我们考虑转移。很明显，对点 i，如果 s_i \ge f(i-1)，那么 f(i)\gets f(i-1)+1。否则，山在这里就断了，f(i) \gets s_i。g() 同理。

最后取 \min \{f(i), g(i)\} 的最大值。