E - Crested Ibis vs Monster

atcoder.jp コンテスト中には解けませんでした。

解法

ナップサック問題です。
動的計画法を用いてdp_tableを埋めていき、右下隅の数字を出力します。計算時間はdp_tableを埋める時間と同じでO(HN)になります。 f:id:tktk0430:20200127004048p:plain

解説

入力例１に対してdp_tableを埋めていく指針を説明します。

[入力例1]
9 3
8 3
4 2
2 1

f:id:tktk0430:20200127004116p:plain ここでXは、魔法1〜2を組み合わせて体力5を減らすための最小の魔力を表します。いきなりこの値を求めるのは困難ですが、上から順番にセルを埋めていくことで、この値を求めることができます。

最も左上からスタートします。ここのセルは魔法1: [8,3]を使って体力1を減らすための最小の魔力を示します。この値は3です。 f:id:tktk0430:20200127004456p:plain 同様に考えてこの行を埋めていくと以下のようになります。 f:id:tktk0430:20200127004335p:plain

2行目は魔法1〜2を組み合わせて体力hを減らすための最小の魔力を算出するフェーズです。ここから上の行の値を参照して値を求める必要が生じます。 f:id:tktk0430:20200127005627p:plain ここで考えるのは魔法2を使うor魔法2を使わない(魔法1だけでその体力を削る)で、どちらがより少ない魔力で達成できるかの検討です。魔法2を使う場合、魔力の最小値は2です。魔法2を使わない場合は、魔法1だけを使って体力1を削る最小の魔力(=上のセルの数字)を持ってきます。ここでは魔法2を使うパターンのほうがより少ない魔力で体力1を削れるので、その値2を入れます。
考える体力が魔法iの攻撃力より低い場合は、魔法iの魔力 or 魔法iを使わないパターンの魔力を考えれば良いです。

f:id:tktk0430:20200127010431p:plain 体力5を削る時も、魔法2を使うor魔法2を使わない(魔法1だけでその体力を削る)で、どちらがより少ない魔力で達成できるかを考えます。この状況において言い換えると以下の2パターンの比較になります。

体力1 (=5-魔法2の攻撃力4)を削るための最小の魔力(2) + 魔法2を使うための魔力(2)
魔法2を使わずに体力5を削るための最小の魔力(3, このセルの直上の数字)

ここでは2.のほうが魔力が少ないので、そちらの値を代入します。
考える体力が魔法iの攻撃力より高い場合は、(体力-魔法iの攻撃力を削るための魔力+魔法iの魔力) or 魔法iを使わないパターンの魔力を考えることになります。
このように考えて2行目を埋めると以下のようになります。 f:id:tktk0430:20200127011158p:plain

3行目も同様に考えます。魔法3を使うパターンor使わないパターンで比較し、セルを埋めていきます。 f:id:tktk0430:20200127011454p:plain f:id:tktk0430:20200127011503p:plain f:id:tktk0430:20200127011514p:plain

このようにして右下のセル、つまり魔法1〜3を組み合わせて体力9を減らすための最小の魔力を求めることができました。

実装

H,N=map(int,input().split())
ls=[list(map(int,input().split())) for i in range(N)]

def dp(H,N,ls):
　#↓0行目に「全てのセルの値が∞の行」をいれることで、1行目だけ特別なロジックを実装する必要がなくなります。
    table=[[float('inf')]*(H+1)] + [[0]*(H+1) for i in range(N)]
    for i in range(1,N+1):
        atk,cost=ls[i-1][0],ls[i-1][1]
        for h in range(H+1):
            if atk>=h:
                table[i][h]=min(table[i-1][h], cost)
            else:
                table[i][h]=min(table[i-1][h], table[i][h-atk]+cost)
    return(table[-1][-1])

print(dp(H,N,ls))