Typical DP Contest A. コンテスト
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の24日目のエントリです．
問題概要
- N問のコンテストがある
- i問目の点数はpiである
- このコンテストで獲得できる得点のパターンは何種類か
解法
- dp[i][j]:=i問目までj点を獲得できるか (できる: 1, できない: 0) とする
- dp[0][0]=1
- dp[i][j-p[i]]ならdp[i+1][j]=1である
※本当は配列を使いまわせばdp[2][10001]の配列で解ける．が，メモリに余裕があるのでそうしなかった．
