百力滋装盒

设前 $i$ 根的最优状态为 $F_i=(B_i,U_i)$，优先最大化盒数 $B_i$，相同时最小化使用根数 $U_i$。不使用第 $i$ 根时得到 $F_{i-1}$。若最后一盒为区间 $k+1,\ldots,i$，前缀和须满足 $Q_i-Q_k\geq X$，得到候选 $(B_k+1,U_k+i-k)$。固定最后一盒后，前面的前缀可以取最优方案，因此该转移覆盖所有方案。子任务 $1$ 可枚举全部 $k$，用 $O(N^2)$ 时间求解。对于完整限制，正重量保证前缀和严格递增。满足 $Q_k\leq Q_i-X$ 的下标依次成为候选，可用指针将每个下标加入一次。维护候选中 $B_k$ 最大、并在相同时 $U_k-k$ 最小的状态，再与 $F_{i-1}$ 比较。时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。

Solution written by GPT6.1