Typical DP Contest A コンテスト

rng_58さんの主催したTypical DP Contestの問題の解法の記事を書いていきます。
コンテストのURLはhttp://tdpc.contest.atcoder.jp/で、問題文などもそこを参照。

方針

dp[得点] := その得点が実現するか
を更新していくDP.


同じ問題は1回しか解けないのでループの向きを降順にする。

ソースコード

int n;
bool can[10001];

int main(){
	cin >> n;
	can[0] = 1;
	rep(i, n){
		int p;
		cin >> p;
		for(int j = 10000; j >= 0; j--) if(can[j]) can[j + p] = 1;
	}
	int ans = 0;
	rep(i, 10001) ans += can[i];
	cout << ans << endl;
	
	return 0;
}