AT274 https://blog.hatena.ne.jp/AT274/ あっとのTECH LOG https://at274.hatenablog.com/ 競プロ DP 問題原文 atcoder.jp 問題要旨 体力が のモンスターがいる。 種類の魔法が使えて、魔法 は、モンスターの体力を 減らすことができるが、 魔力を 消費する。 同じ魔法を何度でも使える時、モンスターの体力を0以下にするためには、最小でどのぐらいの魔力がいるか？ 解法 どう考えてもDPの雰囲気しかしない。というかDPド典型。 として、あとは個数制限なしナップサックと同じ。 計算量は 。ステップ数が 程度になってちょっとビクっとするけど流石に余裕で通る。 実装 を超える部分はまとめてあげると楽。 Magic = [list(map(int, input().split())) for i i… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fat274.hatenablog.com%2Fentry%2F2020%2F01%2F31%2F060000" title="ABC153 E - Crested Ibis vs Monster - あっとのTECH LOG" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20%201%20%5Cleq%20N%20%5Cleq%2010%5E%7B5%7D Hatena Blog https://hatena.blog 2020-01-31 06:00:00 rich https://at274.hatenablog.com/entry/2020/01/31/060000 1.0 100%