ARC026 C - 蛍光灯

問題：C - 蛍光灯

解答：Submission #14082949 - AtCoder Regular Contest 026

解法：dp[x] = xまでは照らされているときのコストの最小値とする。lの値が小さい順に処理してゆく。
(l, r, c)によるdpの更新はt = dp[l]とし、chmin(dp[l], t + c), chmin(dp[l+1], t + c), ..., chmin(dp[r], t + c)である。
実はこれは区間最小のセグメント木を使って高速に実現できる。手順は下記の通り。

1. 区間(l, r)内の最小値をmnとする。
2. 現在のrの値をyとすると、chmin(y, mn + c)する。

なぜこれでうまくいくかは要確認。。