这一道题目可以感觉到，如果没有覆盖全部区间的一次涂色，那么一定会有一个分界点
也就是证如下结论：存在一种最优的方案满足对于任意两次染色：它们的区间要么不交，要么靠后的那次被靠前的那次包含
证明只是反证法然后做一些分类讨论。比如，如果两次染色的区间相交但不包含，你可以缩短靠前的那次的区间使它们变得不相交，但不改变最终的结果
因此如果不存在覆盖全部区间的一次涂色，我们像正常的操作一样枚举分段点就可以了
那么什么时候才会存在覆盖全部区间的一次涂色呢？此时一定有两端点的颜色相同（不然覆盖全部区间的一次涂色没有意义，完全可以缩短或者不要）
此时我们考虑区间\([l,r]\)，其最优方案中，覆盖\(l\)这个点的最后一次操作一定是\(l\)的颜色，我们把这个操作放到最开始做，并且让这个操作的右端点变成\(r\)，显然方案也是合理的，所以有\(f[l][r]=f[l][r-1]\)（当然注意此时换了顺序之后，这个操作可能要缩短一点，其他操作也可能要缩短一点，总之来说左端点附近就不要有重合了）
然而这道题目还可以像消木块那道题目一样考虑最后一段颜色相同的区间什么时候消去，枚举前面颜色相同的区间连起来即可
标签：颜色,覆盖,缩短,涂色,区间,操作 From： https://www.cnblogs.com/dingxingdi/p/17988901