壁壁壁壁壁壁壁

3a51_ · 2025-04-13 15:53:30 · 题解

设 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)。

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

1. 答案是 s_n 位置的函数值，并非整个函数的最小值；
2. 任何位置的加固材料都需 \geq 需要的材料数量，所以需要提前在堆里面放 n 个 0。

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

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