分身並列コーディング [yukicoder No.733] - はまやんはまやんはまやん

前提知識

O(3^N)の部分集合の列挙を使ったbitDP

解法

この問題はbitDPを知っていないと解くのは難しい。
　
ok配列をまず作ろう。
ok[msk] := 集合mskの問題を1人でT時間以内に解けるか
これはO(N2^N)で用意できる。
　
次に、dp配列を作る。
dp[msk] := 集合mskの問題をT時間以内に解くのに必要な最少人数
O(3^N)で部分集合を列挙することで全ての遷移を試す。
msk-msk2からmskへの遷移を考えたときにok[msk2]がtrue（1）であれば、+1で遷移させる。
これをやっていく。

int T, N, t[17];
int ok[1 << 17], dp[1 << 17];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> T >> N;
    rep(i, 0, N) cin >> t[i];

    rep(msk, 0, 1 << N) {
        int sm = 0;
        rep(i, 0, N) if (msk & (1 << i)) sm += t[i];
        if (sm <= T) ok[msk] = 1;
    }

    rep(msk, 0, 1 << N) dp[msk] = inf;
    dp[0] = 0;
    rep(msk, 0, 1 << N) for (int msk2 = msk; msk2 > 0; msk2 = (msk2 - 1)&msk) {
        if (ok[msk2]) chmin(dp[msk], dp[msk - msk2] + 1);
    }
    cout << dp[(1 << N) - 1] << endl;
}