ABC142 E - Get Everything
問題原文
問題要旨
個の宝箱があり、 宝箱 を開けるためには、鍵 が必要になる。
また、 個の鍵セットが売られており、 番目の鍵セットは 円で、 個の鍵のセット を販売している。
鍵が何度でも再利用できるとき、全ての宝箱を開けるのに必要な最小の金額はいくらか?
解法
bitDP。(というか制約がbitDPをやれと言っている。。。)
:=] (鍵の集合 を手に入れるために必要な最小金額) として、 dpテーブルを埋めておけばOK。
遷移元は直前のみなので、 番目までみた時に〜はいらない。(1次元ナップサックと同じですね)
実装
or演算を使うと楽。
あと、入力で与えられる鍵の集合は整数にエンコードしておこう。
N, M = map(int, input().split()) keys = [] for i in range(M): a, b = map(int, input().split()) c = sum([2 ** (c - 1) for c in list(map(int, input().split()))]) keys.append([a, c]) # dp[bs] := 鍵の集合bsを手に入れるのに必要な最小費用 dp = [float('inf')] * (1 << N) dp[0] = 0 for cost, key in keys: for bs in range(1 << N): dp[bs | key] = min(dp[bs | key], dp[bs] + cost) print(dp[-1] if dp[-1] != float('inf') else -1)
感想
いい典型。
巡回セールスマン問題よりも、bitDPの教材としては優れてそう。