壁壁壁壁壁壁壁

设 $s_i$ 表示 $a$ 的前缀和。最基本的想法是 $\text{dp}$，令 $f_i(j)$ 表示考虑到坐标为 $i$ 的位置，使用了 $j$ 个加固材料的最小花费，枚举当前位置有几个加固材料进行转移：$f_i(j)=\min\limits_{0\leq k\leq j-b_i}f_{i-1}(k)+|j-s_i|$。答案为 $f_n(s_n)$。

时间复杂度是 $O(ns_n^2)$ 的，显然过不去，考虑使用 $\text{slope trick}$ 优化。把转移方程的绝对值拆开，可得 $f_i(j)=\min\limits_{0\leq k\leq j-b_i}f_{i-1}(k)+\max(0,j-s_i)+\max(0,s_i-j)$。

所以维护拐点（斜率变化点）只需要先平移，然后取前缀最小值，最后加入两个基本分段线性凸函数即可。注意两个细节：

时间复杂度 $O(n\log n)$，提交记录。

附注：官方题解好像做法不是 $\text{slope trick}$ 优化 $\text{dp}$？但我没太看懂。