看了一下数据范围就知道是区间DP
像这种选择区间的操作，我们一般都会猜一个结论：对区间\([l,r]\)的某种操作序列，如果没有一次操作是覆盖了整个区间的，那么中间一定可以找到一个分段点（这样才可以进行区间DP的枚举分段点的经典转移）
实际上，这道题目也是有类似的性质的
然后放一下正式证明，有兴趣就看一下吧
然后我们就可以设出一个状态：设\(f[i][j][k]\)表示将区间\([i,j]\)变换为\(k\)的最小代价
然后枚举分段点转移即可
但是就像我们上面说的这样，可以使存在一种操作覆盖全部区间的
如果这个操作不是将这个区间改成\(k\)，那么接下来的一次操作肯定是再次覆盖整个区间，将这个区间变成\(k\)（也就可以归入下面的情况）
如果这个操作是将这个区间改成\(k\)，那么之前的操作一定是将\([i,j]\)中所有等于\(k\)的数全部移除
所以我们设\(g[i][j][k]\)表示将区间\([i,j]\)中所有\([k]\)移除掉的最小代价
一种转移方式当然是枚举分段点（就像我们上面说的这样，如果没有某一次操作是覆盖整个区间的话）
如果某一次操作是覆盖整个区间了，那么最后一次操作一定是覆盖整个区间的操作，而且这次操作显然不是将区间变成\(k\)（如果某次覆盖整个区间的操作是将整个区间变成\(k\)，那么下一次操作一定是将区间变成非\(k\)，如果某次覆盖整个区间的操作不是将整个区间变成\(k\)，那么这就是最后一次操作），所以有转移\(g[i][j][k]=g[i][j][l]+1\)，其中\(l!=k\)，意味着我们先将这个区间变成不含\(l\)的，然后最后一次操作将这个区间变成\(l\)
以上操作存在循环转移，为了避免类似情况，我们先进行分段点的转移，然后记录最小值，显然这个最小值不会再改变，然后利用这个最小值去改变区间状态（第二种转移）
这个思想非常秒，可以记住
标签：分段,覆盖,Replace,整个,区间,操作,Segment,转移 From： https://www.cnblogs.com/dingxingdi/p/18027223