\(dp_{i,c} = \)（\(i\) 番目まで決めて、最後に点灯させた色が \(c\)であるときの（操作回数の最小値\(,\) 操作回数最小の上で続けて消灯できる残りの長さの最大値））とする動的計画法を考えます。 同じ状態に対して、操作回数が多いものや消灯できる長さが短いものが最適になることはないため、この動的計画法によって最適解を得ることができます。

計算量は \(O(N)\) となります。

実装例（C++）