DPは他の知識と組み合わせて使う場合が多い。
累積和だったりセグ木だったりコンビネーションだったり。
つまり、DPの問題を安定して解くためには、それら周辺知識が必要不可欠。
周辺知識を増やせばDPの問題も解けるようになってくる。
今日はこちらの問題を解こうとした。
この問題は、DPをConvex-Hull Trickで高速化して解く問題らしいけど、まだConvex-Hull Trickを使ったことがないので解けなかった（そもそも遷移が複雑でわからなかった）。ということで今は、ネット上にあるConvex-Hull Trickの実装を写経している。
写経をすればアルゴリズムがだいたいわかる。
そして、実際に使ってみることでそのアルゴリズムが使えるようになっていく。
そうなれば、考察中にそのアルゴリズムが思い浮かぶようになる。
引き続きConvex-Hull Trickの勉強を進めていく。
