問題リンク 解説 初歩的な動的計画法の問題です。 を、 行目かつ 列目のマスにいる状態とし、残り2つの添字で「どちらの方向から来たか、次に曲がれるか」を保持します。 この動的計画法を と の昇順で回すことで解けます。 このように、典型的な動的計画法…

問題リンク 典型寄せ集めみたいな問題 解説 まず、道の本数が高々 本なので、作れる道を列挙できれば、クラスカル法で空港の数と道のコストの組を計算できる。 空港の建設コストは会社ごとに異なるので、これを変数だと考えると、上に挙げた組は一次関数にな…

Li Chao Tree を書いた. 一次関数 の追加と, での取る値の最小値の取得が、取得したい点の集合のサイズを としてそれぞれ になるデータ構造. 使い道 最適化DPの遷移でこういう式が出てくることがあって, これで高速化ができることがある. JOI で出ることもあ…