きままにものづくり

日々の気付いたことなんかを書いてます。

ARC026 C問題

問題


C: 蛍光灯 - AtCoder Regular Contest 026 | AtCoder

解法

愚直なdpを考える。テーブルは dp[廊下の位置]:=最小コスト とする。これだとO(NL)となりTLEする。
区間lとrの中で最小の値を見つけるのにO(L)の時間を使っている。区間木を用いることでO(N log L)となる。

計算量

 O(N log L)

コード

広告を非表示にする