注意到通过调整可以发现最优解所染色的区间要么不相交，要么先染的严格包含后染的。因此只需要第一层满足长度不超过 $k$，之后可以任意染色，也就是若目标的对应区间有 $d$ 段（每段颜色相同），那么除掉第一次染成全部相同后，还需要 $\lfloor d/2\rfloor$ 次就能达成目标状态。然后就可以 DP 了，用单调队列优化，时间复杂度 $O(n)$。