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

B - 書き換え(Rewrite) の問題を解く。 二次元DPで解くと、 価値の時に個品物を選んだ(or使わなかった)ときの最大値で という漸化式になる。1次元DPを使うと 逆順に更新していくと、重複して更新することが無い。 すべての 価値:j について見て行く。後ろから見ていくと、 (v[i],t[i])を取らない推…