典型ナップサックを1次元配列で解く。

B - 書き換え(Rewrite) の問題を解く。 二次元DPで解くと、 時間の時に個書類を選んだ(or使わなかった)ときの最大値で という漸化式になる。時間のときの最大の価値 となるdp配列を考えます。 ①dp配列を逆順(mから0)に更新していくと、重複して更新することが無い。(更新はすでに見た範囲になります。) ②…