yukicoder：No.798 コレクション
問題
解法
全ての商品をお金を出して買うとすると，答えは
(A_1 + A_2 + ... + A_N) + (B_1 * 0 + B_2 * 1 + B_3 * 2 + ... + B_N * (N - 1))
となる．この式から，B が小さい順に早く購入した方がよいことが分かる．なので，B が小さい順に商品を見ていき，各商品について買うかどうかを DP で最適な解を見つける．
dp(i, j) := (i - 1) 番目の商品までを j 日で手に入れたときの最小の金額
と DP を定義する．遷移は O(1) なので全体で O(N^2)．
解答
本番中，貪欲がダメであることは分かって DP だろうと予想は立てられたが，具体的には思いつかなかったので反省．
