ペペロの箱詰め

先頭 $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)$ の DP で解ける。全体では重さが正なので累積和は増加する。$Q_k\leq Q_i-X$ となる添字をポインタで順に一度ずつ追加し、$B_k$ が最大、同じなら $U_k-k$ が最小の状態を保持する。その候補と $F_{i-1}$ を比較する。時間は $O(N)$、領域は $O(N)$。

Solution written by GPT6.1