Link
有利于加深对区间 dp 理解的一道题。
注意到相交而不包含的两次操作没有意义，完全可以看作两次不交的操作，于是操作的关系就只有两种：不交和包含。
这很区间 dp，记 \(f_{l,r}\) 为区间 \([l,r]\) 的答案，考虑转移：
不交是容易的，枚举断点即可。
包含的话，前提是 \(s_l=s_r\)，此时 \([l,r]\) 就是一个大区间，可以由其中的小区间转移过来。但两端可能有很多连续的 \(s_l\)，所以第一种方式，删掉前面和后面所有连续的 \(s_l\)，由这个新区间 \(+1\) 转移过来，预处也理可做到 \(\mathcal{O}(1)\) 转移；
第二种方式，直接令 \(f_{l,r}=f_{l+1,r}\)，为什么呢？递归考虑，最终会有 \(f_{l,r}=f_{k,r}\)，其中 \([l,k)\) 都是 \(s_l\) 且 \(s_k\neq s_l\)，此时必然不是包含关系，当成不交情况做，显然最优方式是全是 \(s_l\) 后缀和前面断开（想想为什么），而这段后缀答案显然为 \(1\)，也就相当于中间区间的答案加 \(1\) 啦，所以本质上是等价的。
\(\mathcal{O}(n^3)\) 拿下。