Official

F - Big Bridge Editorial by vwxyz


原案:vwxyz

\(j=M,M-1,\dots,0\) の順に答えを求めていきます。
元の料金が \(j\) 以下の商品は料金の合計に影響を与えずにすべて選ぶことができます。
現在の料金の合計が \(l\) 以下になるように元の料金が \(j\) より高い商品を \(k\) 個選んだとき、それらの商品の価値の合計の最大値を \(dp_{k,l}\) とします。
\(j=M\) のとき、
\(dp_{k,l}=\begin{cases}0&(k=0)\\-\infty&(k \neq 0)\end{cases}\)
です。
\(j=m\) から \(j=m-1\) に更新するとき、これまでに \(dp\) に反映させた商品の料金がすべて \(1\) 高くなります。
よって、\(j=m-1\) のときの \(dp_{k,l}\) は \(j=m\) のときの \(dp_{k,l-k}\) です。この更新を①とします。
元の料金が \(m\) の商品も \(dp\) に反映させる必要があります。これを②とします。 これらの更新を行ったうえで、求める答えは \(\displaystyle\max_{0 \leq k \leq N}dp_{k,M}+\sum_{i:c_i\leq j}{v_i}\) です。

計算量について考えます。
②については \(1\) つの商品あたり \(O(NM)\)、合計で \(O(N^2M)\) で更新することができます。
①は、各 \(j\) について更新を行うと \(O(NM^2)\) かかってしまいます。 そこで、②の更新を行うような \(j\) についてだけ①の更新を行うことにし、前回①を行った \(j\) も保持しておくことにすると、①を行う回数を \(O(N)\) 回にすることができ、合計で \(O(N^2M)\) になります。
\(\displaystyle\max_{0 \leq k \leq N}dp_{k,M}+\sum_{i:c_i\leq j}{v_i}\) を求める際にもこの工夫を反映させる必要があることに注意してください。

計算量は合計で \(O(N^2M)\) になります。