题解

思路

对每个值只需关心它的第一次出现位置。设 $f_i$ 表示只考虑前 $i+1$ 个元素时最多能涂色的个数，第 $i$ 个元素保持为 $0$。

若选择某个 $j<i$ 作为上一个保留位置，当 $j\ge \operatorname{first}(a_i)$ 时，可以保留第一次出现的 $a_i$ 与位置 $i$ 作为端点，涂色中间其余元素。因此

$$f_i=\max\left(f_{i-1},\max_{\operatorname{first}(a_i)\le j<i}\{f_j+i-j-1\}\right).$$

做法

子任务 1 可枚举所有涂色状态并搜索合法操作，复杂度 $O(2^n n^3)$。

子任务 2 直接按转移式枚举 $j$，复杂度 $O(n^2)$。

满分做法令 $g_i=f_i-i$，转移化为

$$g_i=-1+\max_{\min(\operatorname{first}(a_i),i-1)\le j<i}g_j。$$

用线段树维护区间最大值，依次求出每个 $g_i$，答案是 $g_{n-1}+n-1$。

复杂度

满分算法时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。