A16021. Tenzing and Balls
编程题
普及/提高-
知识点
题目描述
Tenzing 有 $n$ 个球排成一行。第 $i$ 个球的颜色为 $a_i$。
Tenzing 可以进行任意次以下操作（可能为零次）：
- 选择两个**颜色相同**的球 $i$ 和 $j$（$i < j$），然后将第 $i$ 个到第 $j$ 个（包含两端）之间的所有球从行中删除。被删除的球会从行中消失，剩下的球会靠拢保持相对顺序。
Tenzing 想要**删除尽可能多的球**。请帮助他计算最多能删除多少个球。
Tenzing 可以进行任意次以下操作（可能为零次）：
- 选择两个**颜色相同**的球 $i$ 和 $j$（$i < j$），然后将第 $i$ 个到第 $j$ 个（包含两端）之间的所有球从行中删除。被删除的球会从行中消失，剩下的球会靠拢保持相对顺序。
Tenzing 想要**删除尽可能多的球**。请帮助他计算最多能删除多少个球。
输入格式
第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。
每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。
每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。
保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。
每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。
每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。
保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。
输出格式
对于每个测试用例，输出一个整数——最多能删除的球的数量。
输入输出样例
输入 #1
2 5 1 2 2 3 3 4 1 2 1 2
输出 #1
4 3
说明/提示
- 样例 1：选择 $i = 2, j = 4$（颜色 $2$），删除第 $2$ 到第 $4$ 个球 $[2, 3, 2]$，剩下 $[1, 1]$，再选择 $i = 1, j = 2$（颜色 $1$）删除全部，共删除 $5$ 个……实际上最优是 $4$。
- 样例 2：全部颜色相同，可以直接一次操作删除所有 $6$ 个球。
- 样例 3：所有颜色都不同，无法进行任何操作，删除 $0$ 个。
- 核心思路：$\mathit{dp}[i]$ 表示前 $i$ 个球中最多能删多少个。用 $\mathit{last}[c]$ 记录颜色 $c$ 上一次出现的位置来优化转移。
- 样例 2：全部颜色相同，可以直接一次操作删除所有 $6$ 个球。
- 样例 3：所有颜色都不同，无法进行任何操作，删除 $0$ 个。
- 核心思路：$\mathit{dp}[i]$ 表示前 $i$ 个球中最多能删多少个。用 $\mathit{last}[c]$ 记录颜色 $c$ 上一次出现的位置来优化转移。