Typical DP Contest A問題 : コンテスト

問題. コンテスト

問の問題があり， 問目の配点は 点である．考えうる得点は何通りかを求めよ．
制約： ，　

解法. 動的計画法

を 問目までの問題を解いて得点を とする解き方があるかどうかを表すブール値関数とします．得点が0となる場合 の初期値を true として， 番目の問題を解くことを考えます． が true のとき， 問目までの問題で得点を とする解き方があったので，その解き方に 問目の問題を正解することによって， の値を true とすることができます．したがって，
　
となります． を2次元配列で持ち，上の漸化式で更新すると が答えとなります．ただし， は得点の最大値とします．

上の漸化式の の値を から減少させながら更新すると1次元配列で，
　
を計算することによって答えを求めることができます．

ソースコードを表示（bool型配列を使用）

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int N, p;

    cin >> N;
    const int MAX_S = N * 100;
    vector<bool> score(MAX_S + 1, false);
    score[0] = true;

    for (int i = 0; i < N; ++i) {
        cin >> p;
        for (int j = MAX_S; 0 <= j; --j)
            if (score[j] && j + p <= MAX_S) score[j + p] = true;
    }

    cout << accumulate(score.begin(), score.end(), 0) << endl;

    return 0;
}

他に，bool型の配列ではなくbitsetで持つ解法を載せます．「score << p」 は全ての に対して の計算を行っています．

ソースコードを表示（bitsetを使用）

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    const int MAX_S = 100 * 100 + 1;
    bitset<MAX_S> score(1);
    int N, p;

    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> p;
        score |= score << p;
    }

    cout << score.count() << endl;

    return 0;
}

計算時間：

感想

ナップサック型の動的計画法でテーブルの定義や遷移方法なども同様にできて，本当に典型問題という感じです．