babcs2035 https://blog.hatena.ne.jp/babcs2035/ きろく https://babcs2035.hateblo.jp/ 競技プログラミング yukicoder レベル３問題 問題 解法 解答 問題 yukicoder.me 解法 全ての商品をお金を出して買うとすると，答えは (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)． 解答 y… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbabcs2035.hateblo.jp%2Fentry%2F2019%2F03%2F16%2F123621" title="yukicoder：No.798 コレクション - きろく" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/b/babcs2035/20190316/20190316123527.png Hatena Blog https://hatena.blog 2019-03-16 12:36:21 rich https://babcs2035.hateblo.jp/entry/2019/03/16/123621 1.0 100%