题解

思路推导

设 $f_i$ 表示摆放前 $i$ 本书的最小宽度，$s_i$ 表示前缀和。若最后一层包含第 $j+1$ 到第 $i$ 本书，则它合法当且仅当 $s_i-s_j\le m$，转移代价为这段书的最大长度。因此

$$f_i=\min_{0\le j<i,\ s_i-s_j\le m}\left(f_j+\max_{j<k\le i}h_k\right).$$

直接枚举 $j$ 可解决小规模。由于书长均为正数，对每个 $i$，所有合法的 $j$ 构成一个连续后缀区间，其左端点可以用双指针单调移动。

做法

单调不降情形

若书长单调不降，则最后一段的最大值恒为 $h_i$。转移变成合法区间中 $f_j$ 的最小值加 $h_i$。用单调队列维护滑动窗口内的 $f_j$，即可在线性时间内完成这一层级。

一般情形

固定右端点 $i$，给每个候选断点 $j$ 维护值

$$g_j=f_j+\max_{j<k\le i}h_k.$$

当加入新书 $h_i$ 时，新断点 $i-1$ 的值是 $f_{i-1}+h_i$。对于旧断点，只有原区间最大值不超过 $h_i$ 的连续若干组需要改变，它们的 $g_j$ 都增加“新最大值减旧最大值”。这些组可用单调栈维护；每次弹栈时，对对应的连续断点区间执行区间加。

用带懒标记的线段树维护所有 $g_j$，便可进行区间加、单点写入以及合法断点区间的区间最小值查询。每个单调栈元素至多进栈、出栈一次。

正确性证明

初始时，新断点 $i-1$ 对应只含第 $i$ 本书的最后一层，维护值正确。单调栈把旧断点按其最后一段当前最大值划分成连续组。加入 $h_i$ 后，最大值小于等于 $h_i$ 的组恰好从栈顶连续弹出；对每组增加 $h_i$ 与旧最大值之差后，其所有维护值仍等于定义中的 $g_j$，未弹出的组最大值不变。因此线段树始终精确维护全部候选转移值。

双指针删去的恰是满足 $s_i-s_j>m$ 的断点，所以在线段树的合法区间取最小值，正好得到状态转移式中的全部且仅有合法方案。由归纳法，所有 $f_i$ 都是最优值，最终输出 $f_n$ 正确。

复杂度分析

小规模做法的时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。单调不降做法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。一般做法的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。