C: 蛍光灯 | AtCoder Regular Contest 026

蛍光灯が途切れずに照らしている範囲を左端から右端へ伸ばしていこう。

最適解では、手前で使った蛍光灯をi、次の蛍光灯をjとすると、l[i]<l[j] が成り立つ。なので、事前に蛍光灯をlの昇順にソートしておく。

dp[x] = 0からxまでが途切れずに照らされているときの最小コスト

とする。dp[L]が解。

はじめ

dp[0] = 0である。

蛍光灯をソートされた順にみよう。いま、i番目の蛍光灯の使用を考る。dp[r[i]]が更新されるかもしれない。

蛍光灯は[l[i], r[i]] の範囲を照らすので、

前の範囲 => (重複) => [l[i], r[i]]

のようになっていれば、左端からr[i]まで蛍光灯iを使うことで照らせる。

つまり、その時のコストは

今までのコスト + 蛍光灯iのコスト

= min[l[i]<=x<r[i]](dp[x]) + c

となる。

実装には点更新できるRMQ（セグメント木)で。