Get Everything [AtCoder Beginner Contest 142 E]

https://atcoder.jp/contests/abc142/tasks/abc142_e

前提知識

• bitDP

解説

https://atcoder.jp/contests/abc142/submissions/7771023

Nの制約がかなり小さい。
2¹²は4000くらい。
Mも1000であり、4000×1000は間に合う量である。
bitDPをしよう。
dp[i][msk] := i番目の鍵まで使用するかが決まっていて、開けられる宝箱の集合がmskであるのに必要な費用の最小値
ここまで来ていて、bitDPを理解していればそんなに難しくはない。
予め「takara[i] := i番目の鍵を使用したときに開けられる宝箱の集合」を作っておけば、実装がスムーズになる。

int N, M, A[1010], B[1010], takara[1010];
int dp[1010][1 << 12];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        cin >> A[i] >> B[i];
        rep(j, 0, B[i]) {
            int c;
            cin >> c;
            c--;
            takara[i] |= 1 << c;
        }
    }

    rep(i, 0, M + 1) rep(msk, 0, 1 << N) dp[i][msk] = inf;
    dp[0][0] = 0;

    rep(i, 0, M) rep(msk, 0, 1 << N) {
        chmin(dp[i + 1][msk], dp[i][msk]);
        chmin(dp[i + 1][msk | takara[i]], dp[i][msk] + A[i]);
    }

    int ans = dp[M][(1 << N) - 1];
    if (ans == inf) ans = -1;
    cout << ans << endl;
}