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; }