题解

思路

令 $dp_i$ 表示已经使编号不超过 $i$ 的某棵树成为当前最大已砍倒编号，并为之后工作准备好时的最小代价。初始电量可直接砍倒高度为一的第一棵树，故 $dp_1=0$。若下一个关键编号是 $i$，此前最大编号为 $j<i$，把第 $i$ 棵树锯 $a_i$ 次的充电贡献为 $a_i b_j$，所以

做法

每个 $j$ 对应直线 $y=b_jx+dp_j$，需要按递增的 $x=a_i$ 查询最小值。斜率 $b_j$ 严格递减，因此维护下凸包；查询点也递增，可以从队首单调弹出。中间分支在整数域 $[1,10^5]$ 上使用 Li Chao 树；独立 Oracle 对所有实际 $a_i$ 离散化后使用 Li Chao 树。

正确性证明

转移枚举了最后一次把当前最大已砍倒编号从 $j$ 更新为 $i$ 的全部可能，费用恰为已有最优费用加 $a_i$ 次按 $b_j$ 充电，故动态规划正确。凸包只删除在任何后续递增查询点都不可能成为最小值的直线，队首比较给出当前横坐标的最小值，因此优化不改变转移结果。

复杂度

单调凸包实现时间复杂度 $O(n)$，空间复杂度 $O(n)$。