天增与彩球：题解

思路

令 $dp_i$ 表示只考虑原序列前 $i$ 个球时最多能够删除的球数，$dp_0=0$。

最后一个球可以不参与任何新操作，此时答案为 $dp_{i-1}$。若最后一次新操作的两个端点是 $j$ 和 $i$，其中 $j<i$ 且 $a_j=a_i$，那么在它之前只能使用前 $j-1$ 个位置，随后一次删除区间 $[j,i]$，得到

$$dp_i=\max\left(dp_{i-1},\max_{j<i,\ a_j=a_i}\{dp_{j-1}+i-j+1\}\right).$$

这一定可行：先完成前 $j-1$ 个位置中的操作，再删除当前仍相邻区间中从原位置 $j$ 到原位置 $i$ 的所有球。反过来，任意最优方案若使用了位置 $i$，取包含它的最后一次删除操作，其左端点必为某个同色位置 $j$，操作前能从更左侧删除的数量至多为 $dp_{j-1}$，因此转移也给出了上界。

做法

子任务 1：状态搜索

当 $n\le10$ 时，用一个二进制掩码表示尚未删除的原位置。枚举当前序列中所有同色端点，删除它们之间的所有剩余位置并递归，记忆化每个掩码的最优值。该方法直接模拟题意，最坏状态数为 $2^n$，每个状态枚举 $O(n^2)$ 对端点。

子任务 2：二次动态规划

直接按上述公式枚举 $i$ 与所有 $j<i$，时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

子任务 3：按颜色维护最优转移

把第二项改写为

$$i+\max_{j<i,\ a_j=a_i}(dp_{j-1}-j+1).$$

对每种颜色 $c$ 维护

$$best_c=\max_{j<i,\ a_j=c}(dp_{j-1}-j+1).$$

处理位置 $i$ 时，先用旧的 $best_{a_i}$ 更新 $dp_i$，再把位置 $i$ 作为未来区间的左端点，用 $dp_{i-1}-i+1$ 更新 $best_{a_i}$。每个位置只做常数次操作。

复杂度

• 状态搜索：$O(2^n n^2)$ 时间、$O(2^n)$ 空间；
• 二次动态规划：$O(n^2)$ 时间、$O(n)$ 空间；
• 完整算法：每个测试用例 $O(n)$ 时间、$O(n)$ 空间。

所有测试用例的长度总和不超过 $2\times10^5$，因此完整算法满足限制。

边界情况

• 所有颜色互不相同时不能进行操作，答案为 $0$；
• 所有颜色相同时可一次删除全部球，答案为 $n$；
• 更新同一颜色的 best 时必须使用 $dp_{i-1}$，否则会把包含位置 $i$ 的方案错误地再次用作以 $i$ 为左端点的历史状态；
• 区间长度为 $i-j+1$，两个端点都要计入。