Typical DP Contest A - コンテスト

問題リンク : A: コンテスト - Typical DP Contest | AtCoder

解法 :
bool dp[i] := i が作れるならtrue, otherwise false

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int n;
bool dp[10001];

int main() {
  dp[0] = true;
  cin >> n;
  rep(i,n) {
    int tmp;
    cin >> tmp;
    for(int j=10000;j>=0;j--) if( dp[j] ) dp[j+tmp] = true;
  }
  int cnt = 0;
  rep(i,10001) cnt += dp[i];
  cout << cnt << endl;
  return 0;
}