No.026 C

蛍光灯は $l_i$ でソートしておく.

$i$ 番目の蛍光灯までを見たときに西側から $j$ までの範囲をすべて照らすための最小費用を $C(i,j)$ とすると,

$$C(i,j) = \begin{cases} \min_{l_i \leq k \leq r_i}(C(i-1, k) + c_i) & (l_i \leq j \leq r_i) \\ C(i-1, j) & (otherwise) \end{cases}$$

となる. ただし, $C(0, *) = \infinit$ としておく.

しかし, よく見ると $C(i, j)$ をすべて更新する必要はなく, $C(i, r_i)$ だけ更新しても問題はない.

区間内最小値を高速に計算できるよう, $C$ はセグメントツリーに突っ込んでおく.