Typical DP Contest A:コンテスト

問題文

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

解法

dp[i][j]:i個目までで得点をjにできるか

とした。

コード

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

bool dp[10001];
int main(){
    int n;
    cin>>n;
    dp[0]=true;

    for(int i=0;i<n;i++){
        int p;
        cin>>p;
        for(int j=10000;j>=0;j--){
            if(j-p<0)break;
            dp[j]|=dp[j-p];
        }
    }

    int cnt=0;
    for(int i=0;i<=10000;i++)if(dp[i])cnt++;
    cout<<cnt<<endl;
    return 0;
}