题解中只给出了算法，绝大多数题解没有给出证明。

我花了半个小时也没有证出来为什么这是对的。

我想到的证明如下：

• 考虑一次染色，显然它染色的结果会有一部分保留到终止状态。
• 然后没有保留到终止状态的位置集合构成了若干个区间，由于新的染色不会跨过多个区间（否则第一次染色的结果就没被保留）所以每个区间是独立的。
• 区间 DP，时间复杂度 $O(n^3)\sim O(n^4)$，即对于每种颜色做区间 DP。