ARC128D

· · 题解

结论题。

题意是问有多少种保留位置合法，于是想到令 dp_i 为以 i 作为最后一个保留位置的方案数，则转移方程形如 dp_i = \sum dp_j\text{able}(i,j)，其中 \text{able}(i,j) 为对于 a[i:j]，仅保留 a_i,a_j 是否合法。

现在的重头戏就是探寻 \text{able}(i,j) 的性质。

显然 j=i+1 时一定有解。除此之外当存在两个连续相等字母时无解。但是这是充要条件吗？可以轻易地想到 1010101 串，你找不出来一种方案。事实上，除了 101 字符串删中间就完了之后，一切恰好由两种字符串组成的串都是 1010101010 型，删掉一个位置之后就会出现相同相邻，无解。

但是这是充要条件吗？

断言：当有至少 3 种字符时，一定有解。

证明：考虑随便选择一个 i 使得 a_{i-1},a_i,a_{i+1} 互不相等。如果 a_i 只有一个数的话，直接不断删左邻居（一定合法，因为如果左邻居与左左邻居相等，那么违反“相邻数不等”。由于 a_i 唯一，所以 a_i 一定不等于左邻居）然后不断删右邻居，最后一定为 101，直接删中间即可。

否则删除 a_i 即可转化为序列长度 -1 的子问题。（不需要专门注意单一颜色，把其削到 1 次之后再转化为前述情况）。

观察到如果 [j,i] 违背“相邻不等，那么 [j-1,i] 违背相邻不等。如果 [j,i] 种类数至少为 3，那么 [j-1,i] 种类数至少为 3。所以满足相邻不等，并且种类数至少为 3 的 j 是一个区间，可以前缀和区间求和。对于 j-1 以及 j-2 带来的 101 单独处理即可。双指针即可处理出 j 所在的区间。前缀和即可。

时间复杂度 O(n)。