公式解説と同様の考察により予め \(W+D\) の昇順にソートしてよいです。

\(O(N^2)\) 解法

\(\mathrm{DP}[i][j]\) = \(i\) 番目段ボール箱までで \(j\) 個積み上げるときの重さの合計最小値（不可能なら \(\infty\) ）

\(O(N\log N)\) 解法

\(\mathrm{DP}[i]\) で、列 \((\mathrm{DP}[i][0],\mathrm{DP}[i][1],\mathrm{DP}[i][2],\dots)\) を表すことにします。

以下の \(3\) 点を証明します。

• \(\mathrm{DP}[i]\) は \(j\) の列として単調増加である
• \(\mathrm{DP}[i]\) の階差は広義単調増加である
• \(\mathrm{DP}[i+1]\) の階差は \(\mathrm{DP}[i]\) の階差に、順序を保って \(W\) を挿入したものか、それから \(\infty\) でない末尾要素を削除したものである。

\(i\) に関する帰納法によります。 3 点目が示せれば 1,2 点目明らかなので、3 点目のみ示します。

\(i=0\) のときの成立は明らかです。\(i\geq 1\) のときを考えます。

\(k\) を \(\mathrm{DP}[i][k]\) が \(\infty\) ではない最大の整数とします。\(k\geq 1\) が成り立ちます。また、 \(W_{i+1}, D_{i+1}\) を単に \(W,D\) と書きます。

\(O(N^2)\) 解法における DP テーブルの更新式 if(dp[i][j-1] <= D) dp[i+1][j] = min(dp[i][j], dp[i][j-1] + W) を思い浮かべながら、次の 3 つのケースに分けて考えます。

• \(\mathrm{DP}[i][k]\leq D\) のとき
  このとき、 DP テーブル更新式の if 文の条件に全ての \(j\) が該当するため、全ての \(j\) で更新が行われ、結果として階差には \(W\) が挿入されます。
• \(\mathrm{DP}[i][k]>D\) かつ \(\mathrm{DP}[i][k]-\mathrm{DP}[i][k-1]<W\) のとき
  DPテーブルが更新される箇所はありません。これは「階差の列に \(W\) を順序を保って(末尾に)挿入し、末尾要素を削除する」と同じです。
• \(\mathrm{DP}[i][k]>D\) かつ \(\mathrm{DP}[i][k]-\mathrm{DP}[i][k-1]\geq W\) のとき
  \(W+D\) の昇順に考えていることから、 \(\mathrm{DP}[i][k] \leq W+D\) であることに注意すると、\(\mathrm{DP}[i][k-1]\leq DP[i][k]-W \leq (D+W)-W \leq D\) なので、 \(j \leq k\) では DP テーブル更新式の if 文の条件を満たし、結果として「階差の列に \(W\) を挿入して末尾要素を削除する」となります。

よって、 DP テーブルや \(\mathrm{DP}[i]\) そのものを持つ代わりにその階差の多重集合と \(\mathrm{DP}[i][k]\) 即ち階差の総和を保持することで \(O(N\log N)\) でこの問題を解くことができます。