by rvalue
看到题目首先考虑最优解是长啥样的
构造一下就会发现最优解一定是从一个 \(i(1\leq i\leq n)\) 开始一直放水放到 \(n\) . 因为如果中间有中断的话只有最后连续的一段对第 \(n\) 层是有影响的
那么可以想到一个朴素的 \(O(n^2)\) 暴力, 即枚举这个 \(i\) 然后模拟放水过程, 能自动放就自动放, 不能就花钱放.
原数据范围 \((1.5\times 10^4)\) 这样实际上就可以过了, 因为常数非常小
接着考虑一个常用思想, 就是计算某个费用会在什么情况下产生贡献.
我们定义 \(c_i\) 为从第 \(i\) 层开始放水一直放到第 \(n\) 层所需的费用. 考虑第 \(k\) 层的强制放水花费会对整个 \(\left\langle c_i \right \rangle\) 产生什么样的影响. 显然有当且仅当从第 \(i\) 层到第 \(k\) 层的总水量都不足以使第 \(k\) 层自动减压时 \(c_i\) 中会包含第 \(k\) 层的强制放水费用. 因为当 \(k\) 不变时总水量随着 \(i\) 的减少而单调增加, 所以合法的 \(i\) 必然是比 \(k\) 小的连续一段, 二分找到最小的 \(i\) , 把最小的 \(i\) 到 \(k\) 之间的所有 \(c_i\) 都加上 \(k\) 的花费即可. 而这个操作可以通过简单的前缀和解决. 总时间复杂度是 \(O(n\log n)\).
原文：https://www.cnblogs.com/rvalue/p/13322258.html