JOI 21二次予選 C イベント巡り(難易度8)
$ dp_{i, j} := $ i個のイベントに参加して$ j番目の都市にいるときの時間の最小値(そのような場合が起こらない場合INF) としてDPをしていく.
DPの遷移だが, 二分探索を用いる. 具体的には同じ都市の場合, 異なる都市の場合の両方, 町1と町2のイベントの開催時刻を持っておいて最小時間を求める.
時間は小さければ小さいほどよいのでこのDPですべての場合が網羅できる.
答えは値がINFでないような最大の$ dp_{i,j}の$ iとなる.