PAST1I

https://gyazo.com/c2448c08a7e7e39a1cf0cef3c676a36a

考えたこと

1000個のセットからいくつか選んで、コスト最小で10個の部品を揃える問題

2^1000は大きすぎるが、1000×2^10なら10^6ぐらいなので余裕

2^10の部分集合を定義域、それを達成する最小コストを値域とするDP

空集合を0、他をINFで初期化してセットごとにchmin

公式解説OK

AC

code:python

def solve(N, M, SS, CS):

INF = 9223372036854775807

for i in range(M):

for src in range(2 ** N):

dst = s | src

if ret == INF:

return -1

return ret