Typical DP Contest A - コンテスト

解法

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    vector<int> p(N);
    for(int i=0; i<N; ++i) {
        cin >> p[i];
    }
    vector<bool> dp(10001);
    dp[0] = true;
    for(int i=0; i<N; ++i) {
        for(int j=10000-p[i]; j>=0; --j) {
            dp[j+p[i]] = dp[j+p[i]] | dp[j];
        }
    }
    cout << count(dp.begin(), dp.end(), true) << endl;
}