Paint

题意翻译

给定长度为 $n$ 的颜色序列 $a_i$，每次你可以选择任意长度的**连续且颜色相同**的一段位置，将其全部变成任意同一种颜色，问你最少总共需要多少次操作才能使得整个序列颜色相同。 **限制：** 每一种颜色初始时在序列中最多只有20个位置（是该种颜色）。 ### 输入格式 首先一个整数 $t\le 1000$，表示数据组数，然后每组数据先输入一个数 $n\le 3000$，然后输入 $n$ 个数 $a_i \le n$，$\sum n \le 3000$。 ### 输出格式 对于每一组数据输出最小操作次数。

题目描述

You are given a $ 1 $ by $ n $ pixel image. The $ i $ -th pixel of the image has color $ a_i $ . For each color, the number of pixels of that color is at most $ 20 $ . You can perform the following operation, which works like the bucket tool in paint programs, on this image: - pick a color — an integer from $ 1 $ to $ n $ ; - choose a pixel in the image; - for all pixels connected to the selected pixel, change their colors to the selected color (two pixels of the same color are considered connected if all the pixels between them have the same color as those two pixels). Compute the minimum number of operations needed to make all the pixels in the image have the same color.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^3 $ ). The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 3\cdot10^3 $ ) — the number of pixels in the image. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — the colors of the pixels in the image. Note: for each color, the number of pixels of that color is at most $ 20 $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3\cdot10^3 $ .

输出格式

For each test case, print one integer: the minimum number of operations needed to make all the pixels in the image have the same color.

输入输出样例

输入样例 #1

3
5
1 2 3 2 1
4
1 1 2 2
5
1 2 1 4 2

输出样例 #1

2
1
3

说明

In the first example, the optimal solution is to apply the operation on the third pixel changing its color to $ 2 $ and then to apply the operation on any pixel that has color $ 2 $ changing its color and the color of all pixels connected to it to $ 1 $ . The sequence of operations is then: $ [1, 2, 3, 2, 1] \to [1, 2, 2, 2, 1] \to [1, 1, 1, 1, 1] $ . In the second example, we can either change the $ 1 $ s to $ 2 $ s in one operation or change the $ 2 $ s to $ 1 $ s also in one operation. In the third example, one possible way to make all the pixels have the same color is to apply the operation on the first, third and the fourth pixel each time changing its color to $ 2 $ .