Almost Triple Deletions

题意翻译

给定长为 $n$ 的数组 $\{a_n\}$，每次操作可删去数组中相邻的两个不相等的元素（即若 $i\in[1,n), a_i\not=a_{i+1}$，则可以删去 $a_i$ 和 $a_{i+1}$）。求若干次操作后，使得数组内元素全部相等的数组长度的最大值。 多测，$t\le10^3$，$1\le a_i\le n\le5\times10^3$，$\sum n\le10^4$。 Translated by @Sya_Resory

题目描述

You are given an integer $ n $ and an array $ a_1,a_2,\ldots,a_n $ . In one operation, you can choose an index $ i $ ( $ 1 \le i \lt n $ ) for which $ a_i \neq a_{i+1} $ and delete both $ a_i $ and $ a_{i+1} $ from the array. After deleting $ a_i $ and $ a_{i+1} $ , the remaining parts of the array are concatenated. For example, if $ a=[1,4,3,3,6,2] $ , then after performing an operation with $ i=2 $ , the resulting array will be $ [1,3,6,2] $ . What is the maximum possible length of an array of equal elements obtainable from $ a $ by performing several (perhaps none) of the aforementioned operations?

输入输出格式

输入格式

Each test contains multiple test cases. The first line of input contains one integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The following lines contain the descriptions of the test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 5000 $ ) — the length of array $ a $ . The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \le a_i \le n $ ) — the elements of array $ a $ . It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 10\,000 $ .

输出格式

For each testcase, print a single integer, the maximum possible length of an array of equal elements obtainable from $ a $ by performing a sequence of operations.

输入输出样例

输入样例 #1

5
7
1 2 3 2 1 3 3
1
1
6
1 1 1 2 2 2
8
1 1 2 2 3 3 1 1
12
1 5 2 3 3 3 4 4 4 4 3 3

输出样例 #1

3
1
0
4
2

说明

For the first testcase, an optimal sequence of operations would be: $ [1,2,3,2,1,3,3] \rightarrow [3,2,1,3,3] \rightarrow [3,3,3] $ . For the second testcase, all elements in the array are already equal. For the third testcase, the only possible sequence of operations is: $ [1,1,1,2,2,2] \rightarrow [1,1,2,2] \rightarrow [1,2] \rightarrow [] $ . Note that, according to the statement, the elements deleted at each step must be different. For the fourth testcase, the optimal sequence of operations is: $ [1,1,2,2,3,3,1,1] \rightarrow [1,1,2,3,1,1] \rightarrow [1,1,1,1] $ . For the fifth testcase, one possible reachable array of two equal elements is $ [4,4] $ .

题目大意：
给定一个长度为 $n$ 的数组 $\{a_n\}$，每次操作可以删除数组中相邻的两个不相等的元素。求经过若干次操作后，使得数组内元素全部相等的数组长度的最大值。

输入输出数据格式：
输入格式：
- 第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。
- 每个测试用例有两行，第一行包含一个整数 $n$（$1 \le n \le 5000$），表示数组 $a$ 的长度。
- 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示数组 $a$ 的元素。

输出格式：
- 对于每个测试用例，输出一行，包含一个整数，表示通过执行一系列操作后，可以得到数组内元素全部相等的最大长度。

输入输出样例：
输入样例 #1：
```
5
7
1 2 3 2 1 3 3
1
1
6
1 1 1 2 2 2
8
1 1 2 2 3 3 1 1
12
1 5 2 3 3 3 4 4 4 4 3 3
```
输出样例 #1：
```
3
1
0
4
2
```

说明：
- 第一个测试用例中，最优的操作序列是：$[1,2,3,2,1,3,3] \rightarrow [3,2,1,3,3] \rightarrow [3,3,3]$。
- 第二个测试用例中，数组中的所有元素已经相等。
- 第三个测试用例中，唯一的可能操作序列是：$[1,1,1,2,2,2] \rightarrow [1,1,2,2] \rightarrow [1,2] \rightarrow []$。注意，根据题目要求，每一步删除的元素必须不同。
- 第四个测试用例中，最优的操作序列是：$[1,1,2,2,3,3,1,1] \rightarrow [1,1,2,3,1,1] \rightarrow [1,1,1,1]$。
- 第五个测试用例中，可以得到两个相等元素的数组的一个可能是 $[4,4]$。题目大意： 给定一个长度为 $n$ 的数组 $\{a_n\}$，每次操作可以删除数组中相邻的两个不相等的元素。求经过若干次操作后，使得数组内元素全部相等的数组长度的最大值。 输入输出数据格式： 输入格式： - 第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 - 每个测试用例有两行，第一行包含一个整数 $n$（$1 \le n \le 5000$），表示数组 $a$ 的长度。 - 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示数组 $a$ 的元素。 输出格式： - 对于每个测试用例，输出一行，包含一个整数，表示通过执行一系列操作后，可以得到数组内元素全部相等的最大长度。 输入输出样例： 输入样例 #1： ``` 5 7 1 2 3 2 1 3 3 1 1 6 1 1 1 2 2 2 8 1 1 2 2 3 3 1 1 12 1 5 2 3 3 3 4 4 4 4 3 3 ``` 输出样例 #1： ``` 3 1 0 4 2 ``` 说明： - 第一个测试用例中，最优的操作序列是：$[1,2,3,2,1,3,3] \rightarrow [3,2,1,3,3] \rightarrow [3,3,3]$。 - 第二个测试用例中，数组中的所有元素已经相等。 - 第三个测试用例中，唯一的可能操作序列是：$[1,1,1,2,2,2] \rightarrow [1,1,2,2] \rightarrow [1,2] \rightarrow []$。注意，根据题目要求，每一步删除的元素必须不同。 - 第四个测试用例中，最优的操作序列是：$[1,1,2,2,3,3,1,1] \rightarrow [1,1,2,3,1,1] \rightarrow [1,1,1,1]$。 - 第五个测试用例中，可以得到两个相等元素的数组的一个可能是 $[4,4]$。