部品調達 / Procurement [第一回 アルゴリズム実技検定 過去問 I]

https://atcoder.jp/contests/past201912-open/tasks/past201912_i

前提知識

• bitDP

解説

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;
}