1572c

CF1572C Paint 一看感觉很有 dp 的感觉。所以就来吧。 设 $f_{l,r,c}$ 表示区间 $[l,r]$ 选了颜色 $c$ 的答案，先不管怎么转移。 状态太巨大，有种猜结论的冲动：若只保留 $c=a_l$ 和 $c=a_r$，答案依旧正确。 考虑证明：答案只和 $f_{1,n}$ ......