Typical DP Contest A - コンテスト

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_contest

解法

基本的なナップサック問題．
p(i), N <= 100 なので，高々 10^6 のループで終わる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

constexpr int max_p = 10000;

int main() {
    int n; cin >> n;
    vector<int> p(n);
    for(auto& x : p) cin >> x;

    vector<bool> dp(max_p + 1);
    dp[0] = true;
    for(int i = 0; i < n; ++i) {
        for(int j = max_p - p[i]; j >= 0; --j) {
            dp[j + p[i]] = dp[j + p[i]] | dp[j];
        }
    }

    cout << count(dp.begin(), dp.end(), true) << endl;
}