babcs2035 https://blog.hatena.ne.jp/babcs2035/ きろく https://babcs2035.hateblo.jp/ 競技プログラミング AtCoder 500 点問題 問題 解法 解答 問題 atcoder.jp 解法 dp1(b, i) := 今残っている商品が b で，財宝を i 個売却した時に商品を買って取引を終了する場合，得られる最大のスコア dp2(b, i) := 今残っている商品が b で，財宝を i 個売却した時に得られる最大のスコア の２つの DP を考える． dp2 では，この時点で商品を買って取引を終了する場合と，まだ財宝の売却を続けるの２つの選択肢がある．前者を選んだ場合，その時の dp2 の解は dp1 になり，後者を選んだ場合，買えなくする商品を全通り試したなかの最小値になる（相手は解を最小化しようとするから）． dp1 では，も… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbabcs2035.hateblo.jp%2Fentry%2F2018%2F12%2F20%2F185438" title="「みんなのプロコン 2018」：C - 駆引取引 - きろく" 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/20181220/20181220185422.png Hatena Blog https://hatena.blog 2018-12-20 18:54:38 rich https://babcs2035.hateblo.jp/entry/2018/12/20/185438 1.0 100%