storage [OyamaC]

https://www.hackerrank.com/contests/oyamac/challenges/storage

前提知識

• bitsetによる動的計画法高速化

解説

https://www.hackerrank.com/contests/oyamac/challenges/storage/submissions/code/1321979183

見た目、ナップサック問題に近いし、yes/no系動的計画法でよく見る形でもあるので、
yes/no系動的計画法で解くことを考えてみよう。

以下のようなDPが思いつく。

dp[i][k][w] := i個目までの荷物を使って、k個の荷物を選択したときに、容量wが達成できるか
dp[i][k][w] = dp[i - 1][k][w] | dp[i - 1][k - 1][w - W[i]]

DPのサイズは10³10³10³なので、かなりギリギリ。
だが、この遷移はbitset高速化ができる形になっている。

最後のwをbitsetのbitで表現することにすると、更新式は以下のように変わる。
dp[i][k] = dp[i - 1][k] | (dp[i - 1][k - 1] << W[i])
これで/64するので間に合うようになる。

int A, N, K, W[1010];
bitset<1010> dp[2][1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> N >> K;
    rep(i, 0, N) cin >> W[i];

    dp[0][0].set(0);
    rep(i, 0, N) {
        int cu = i % 2;
        int ne = 1 - cu;
        rep(k, 0, K + 1) dp[ne][k].reset();

        rep(k, 0, K + 1) {
            dp[ne][k] |= dp[cu][k];
            dp[ne][k + 1] |= dp[cu][k] << W[i];
        }
    }

    rep(k, 0, K + 1) if (dp[N % 2][k][A]) {
        cout << "YES" << endl;
        return;
    }
    cout << "NO" << endl;
}