对于 CF1107E 中 dp 状态设计的一点想法

不太想发到洛谷讨论区，就往这里放了。

我觉得现有的题解都没说明白为什么本题的状态和转移能覆盖所有情况，并且感觉也非常不自然，没见过的话感觉挺难发现这么一个东西。

然而这个 dp 其实是可以自然地推导出来的。

首先发现这个过程非常难以描述，主要原因在于很难刻画一个局面。然而，如果知道一个局面是什么样的，转移是简单的。

因此我们考虑 时光倒流，直接考虑最后一次操作，这时的局面非常简单：一定是删掉全部的数。

然后考虑这次操作在原序列上的表现：选定若干个字符相等的位置 \(s_1,s_2,\dots,s_k\)，分割出来若干段形如 \((s_i,s_{i+1})\) 这样的区间，因为我们是倒着操作的，所以这些分割出来的区间不会再有交集，直接做下去就好了。

为了转移，我们定义辅助数组 \(g(l,r,k)\)：表示我们选了 \(k\) 个位置留作最后操作的最大价值。转移并不困难，然后再得到 \(f(l,r)\) 即可。

发现这个东西其实和 [THUSC 2016] 成绩单 描述的 dp 是很类似的。

回过头来看一看我们干了一件什么事，因为删掉 \((s_i,s_{i+1})\) 这样的区间的顺序并不重要，我们可以这样从右往左考虑这个过程：

• 保留一个位置，并删掉和前一个保留的位置之间的区间。要求保留的位置上的字符相同。

这个 保留的位置 就是 luogu 题解里面的 \(f(l,r,k)\) 中 \(k\) 的含义，当然也有一点不同：允许过程中把这个 \(k\) 清空。

直接正着想的话可能也能感受到这个过程，但毕竟不怎么自然啊。

所以这种过程性较强的题目，从最终局面出发始终可以作为一种选择。