問題. コンテスト
問の問題があり, 問目の配点は 点である.考えうる得点は何通りかを求めよ.
制約: ,
解法. 動的計画法
を 問目までの問題を解いて得点を とする解き方があるかどうかを表すブール値関数とします.得点が0となる場合 の初期値を true として, 番目の問題を解くことを考えます. が true のとき, 問目までの問題で得点を とする解き方があったので,その解き方に 問目の問題を正解することによって, の値を true とすることができます.したがって,
となります. を2次元配列で持ち,上の漸化式で更新すると が答えとなります.ただし, は得点の最大値とします.
上の漸化式の の値を から減少させながら更新すると1次元配列で,
を計算することによって答えを求めることができます.
他に,bool型の配列ではなくbitsetで持つ解法を載せます.「score << p」 は全ての に対して の計算を行っています.
計算時間:
感想
ナップサック型の動的計画法でテーブルの定義や遷移方法なども同様にできて,本当に典型問題という感じです.