Typical DP Contest A - コンテスト

問題文 : コンテスト

解法 :
dp[x] : 得点x を得ることが出来るか？ としてDP. dp[x] が真⇒dp[x + a[i]] が真となる事を利用してO(N*sum) で計算可能.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>

using namespace std;

int dp[10001];

int main()
{
	int N;
	scanf("%d", &N);
	
	dp[0] = 1;
	for (int i = 0; i < N; i++){
		int a;
		scanf("%d", &a);
		
		for (int j = 10000; j >= a; j--)
			if (dp[j - a]) dp[j] = 1;
	}
	
	int ans = 0;
	for (int i = 0; i <= 10000; i++) ans += dp[i];
	
	printf("%d\n", ans);
	return (0);
}