PAST1I
考えたこと
1000個のセットからいくつか選んで、コスト最小で10個の部品を揃える問題
2^1000は大きすぎるが、1000×2^10なら10^6ぐらいなので余裕
2^10の部分集合を定義域、それを達成する最小コストを値域とするDP
空集合を0、他をINFで初期化してセットごとにchmin
公式解説OK
AC
pythondef solve(N, M, SS, CS):
INF = 9223372036854775807
table = [INF] * (2 ** N)
table[0] = 0
SS = [int(s.replace("Y", "1").replace("N", "0"), 2) for s in SS]
for i in range(M):
s = SS[i]
for src in range(2 ** N):
dst = s | src
table[dst] = min(table[dst], table[src] + CS[i])
ret = table[2 ** N - 1]
if ret == INF:
return -1
return retRelated Pages
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁dp×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
- →past5×past202012×アルゴリズム実技検定×past過去問練習202012×past5e×past5f×past5g×past5h×past5i×past5j×PAST5K×past5l×past5m×past5n×past5o×番兵×地図読み込み時に番兵をつける×ゴールをスタートにする×ゴールを一つにする×ダイクストラ法×bit_dp×期待値dp×二次元の片方を時間軸にする×past2n→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]