DPは他の知識と組み合わせて使う場合が多い。 累積和だったりセグ木だったりコンビネーションだったり。 つまり、DPの問題を安定して解くためには、それら周辺知識が必要不可欠。 周辺知識を増やせばDPの問題も解けるようになってくる。 今日はこちらの問題…

次のようなコードをエディタのスニペットに登録しておくと楽。 struct $1 { $2 bool operator<(const $1 &that) const { #define lt(x) if (x != that.x) return x < that.x; #define gt(x) if (x != that.x) return x > that.x; $0 #undef gt #undef lt ret…

こちらの問題を解いたのだけど、証明がまだきちんとできないことに気付いた。 証明したいのは「既に食べるピザが決まっているとき、価格の降順でソートして前から有料→無料→有料→…のように買うのが最善」という命題。交互に食べることが最善だなんてどうやっ…