More Cow Photos

题目描述

奶牛们今天特别淘气！Farmer John 只想给排成一列的奶牛拍张照片，但它们总是在他按下快门之前乱动。

具体来说，FJ 有 $N$ 头奶牛（$1 \le N \le 10^5$），每头奶牛都有一个从 $1$ 到 $N$ 的整数身高。FJ 想要拍一张奶牛排成一列、且顺序非常特定的照片。若从左到右排成一列时奶牛身高为 $h_1, \dots, h_K$，他希望这些身高满足以下三个性质：

1. 他希望奶牛身高先不下降后不上升。形式化地，必须存在一个整数 $i$ 使得 $h_1 \le \dots \le h_i \ge \dots \ge h_K$。
2. 他不希望有任意两头相邻奶牛身高完全相同。形式化地，对所有 $1 \le i < K$，都有 $h_i \neq h_{i+1}$。
3. 他希望照片是对称的。形式化地，若 $i + j = K+1$，则 $h_i = h_j$。

FJ 希望照片中包含尽可能多的奶牛。具体而言，FJ 可以移除一些奶牛，并将剩下的奶牛重新排列。请计算在满足上述限制的前提下，FJ 的照片最多能包含多少头奶牛。

输入格式

你需要回答多个测试用例。 输入第一行包含一个整数 $T$（$1 \leq T \leq 10^5$），表示测试用例数量。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含一个整数 $N$。第二行包含 $N$ 个整数，表示这 $N$ 头可用奶牛的身高。 奶牛身高在 $1$ 到 $N$ 之间。 保证所有测试用例中 $N$ 的总和不超过 $10^6$。

输出格式

输出 $T$ 行，第 $i$ 行为第 $i$ 个测试用例的答案。 每行输出一个整数，表示 FJ 最多能在照片中包含的奶牛数量。

2
4
1 1 2 3
4
3 3 2 1

3
1

提示

对于第一个测试用例，FJ 可以选择身高为 $1$、$1$ 和 $3$ 的奶牛，并将它们重新排列为 $[1,3,1]$，从而满足所有条件。对于第二个测试用例，FJ 可以选择身高为 $3$ 的奶牛并形成一张合法的照片。 SCORING: Inputs 2-3: $T\le 100, N \le 7$ Inputs 4-5: $T \le 10^4$, all cows will have height at most 10. Inputs 6-11: No additional constraints. Problem credits: Nick Wu

标签: USACO|2025|Bronze

来源

USACO|2025|Bronze