https://atcoder.jp/contests/past201912-open/tasks/past201912_i
前提知識
解説
https://atcoder.jp/contests/past201912-open/submissions/9257465
bitDPを知らないと解くのは難しい。
もしわからない場合は、bitdpでググって概要を理解してきて欲しい。
さて、bitDPを使うと分かっていればそんなに難しく無いだろう。
dp[msk] := 部品を集合msk分持っているときに必要な金額の最小値
あるセットを複数買ってしまう可能性を心配するかもしれないが、同じセットを2回買うと、
必ず無駄になってしまうので、特に考える必要はない。
int N, M; int MSK[1010], C[1010]; ll dp[1 << 10]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; rep(i, 0, M) { string S; cin >> S >> C[i]; fore(c, S) { MSK[i] <<= 1; if (c == 'Y') MSK[i] |= 0x01; } } rep(msk, 0, 1 << N) dp[msk] = infl; dp[0] = 0; rep(msk, 0, 1 << N) rep(i, 0, M) chmin(dp[msk | MSK[i]], dp[msk] + C[i]); ll ans = dp[(1 << N) - 1]; if (ans == infl) cout << -1 << endl; else cout << ans << endl; }