题解：AT_abc359_e [ABC359E] Water Tank

· · 题解

以下称第 i 个隔板和第 i-1 个隔板之间的区域被称为第 i 个空格，我们要输出的答案显然就是把第 i 个格子注满所需注入的水量再加 1。

对于每一个 i，我们可以先求出 a_i 到 a_{i-1} 中最后一个 >a_i 的 a_j，定义这样的 j 叫做 pre_i。我们就可以先求出注满第 pre_i 个方格的代价，然后再注满 pre_i 到 i 之间的区域，就是结果。

问题就变成如何求 pre_i。

可以先令 pre_i \leftarrow i-1，然后一直令 pre_i \leftarrow pre_{pre_i}，直到 pre_i > a_i 或 pre_i = 0。

赛事代码。