Time-6 - Make you Stronger

この問題は個数制限なしナップザック問題を問います。

$T=0$ のとき...

一旦簡単のため $T=0$ のことについて考えてみましょう。そうすると次の問題と同値であることが言えます。

• 子スライムを何匹か繰り返し選び、それらのぷるぷる度の合計値が $K$ 以下となるように親スライムに合成した後、考えられる価値の最大値はいくつか？

これは、単なる個数制限なしナップザック問題であることがわかります。例えば

• $\text{dp}[i][j]:=$ $i$ 個目の子スライムを選んでぷるぷる度の合計を $j$ にしたときの価値の最大値

といったDP(動的計画法)テーブルを定義しましょう。最初 $i=1,2,...,N,\ j=0,1,2,...,K$ に対して $\text{dp}[i][j]=0$ と初期化します。
その後、次のように遷移式を立てます。

• $\text{dp}[i+1][j]=\text{dp}[i][j]$ (子スライム $i$ を $1$ 匹も選ばないとき)
• $\text{dp}[i+1][j]=\max(\text{dp}[i+1][j],\text{dp}[i+1][j-A_i]+B_i)$ (子スライム $i$ を $1$ 匹以上選ぶ場合)

最終的に答えるべき値は $\max(\text{dp}[N][j])$ です。
※この漸化式の説明はここでは省略します。Webでは分かりやすい記事も転がってるはずなので、そちらを参考にしてください。

$T\ge 1$ のとき...

$T=0$ を考えた上で、元の問題を考えてみます。
実は、$t=0,1,2,...,T$ におけるそれぞれの子スライムのステータスを保管しながら、同じように動的計画法を用いることで解くことが可能です。

入力では $t=0$ の場合のみですが、それに $t=1,2,...,T$ を同じように入力している、と考えると分かりやすいと思われます。

以上から全体で $O(NTK)$ で実装することができます。以下が解答例(C++,Python)となります。

追記(14:42更新)

実はこの問題、答えが -1 になることはありません。$K=0$ だとしてもスライムを一匹も選ばないことが最適であるためです。

(下のコードは追記前のコードにしてあります)

• C++

• Python