月 の 上

paiza消火できなかった

火消し人の奴、興味なかったけど、大学の人がやってたの見て急にやりたくなった

昔勉強した知識だとこういうのはDPでできるはずって思って書いてみたけどテストケース3/7しか通らなかった
偏差値44とか言っててショックすぎる

if __name__ == '__main__':
    m = input()
    n = input()

    dp = { 0: 0 }
    answer = float('inf')

    for l in range(n):
        num, cost = map(lambda x: int(x), raw_input().split())
        keys = dp.keys()
        for src in keys:
            dst = src + num
            if dst in keys:
                dp[dst] = min(dp[dst], dp[src] + cost)
            else:
                dp[dst] = dp[src] + cost

            if dst >= m:
                answer = min(answer, dp[dst])

    print(answer)

ぐぐったら解答公開してる人いた

コード読んだけど、簡単な解法の方は自分のコードと大体同じ事してるような気がする。
どこがおかしいんだ……