#PU1516. USACO 2025 US Open Contest, Bronze — Problem 2. More Cow Photos

    ID: 1670 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>USACO赛事:open25来源:usaco.orgscoring:equal_test_cases单调栈哈希

USACO 2025 US Open Contest, Bronze — Problem 2. More Cow Photos

USACO 2025 US Open Contest, Bronze — Problem 2. More Cow Photos

题目描述

The cows are in a particularly mischievous mood today! All Farmer John wants to do is take a photograph of the cows standing in a line, but they keep moving right before he has a chance to snap the picture. Specifically, each of FJ's NN cows (1≤N≤105)(1 \le N \le 10^5) has an integer height from 11 to NN. FJ wants to take a picture of the cows standing in line in a very specific ordering. If the cows have heights h1,…,hKh_1, \dots, h_K when lined up from left to right, he wants the cow heights to have the following three properties: He wants the cow heights to increase and then decrease. Formally, there must exist an integer ii such that h1≤⋯≤hi≥⋯≥hKh_1 \le \dots \le h_i \ge \dots \ge h_K. He does not want any cow standing next to another cow with exactly the same height. Formally, hi≠hi+1h_i \neq h_{i+1} for all 1≤i<K1 \le i < K. He wants the picture to be symmetric. Formally, if i+j=K+1i + j = K+1, then hi=hjh_i = h_j. FJ wants the picture to contain as many cows as possible. Specifically, FJ can remove some cows and rearrange the remaining ones. Compute the maximum number of cows FJ can have in the picture satisfying his constraints.

输入格式

You have to answer multiple test cases. The first line of input contains a single integer TT (1≤T≤1051 \leq T \leq 10^5) denoting the number of test cases. TT test cases follow. The first line of every test case contains a single integer NN. The second line of every test case contains NN integers, the heights of the NN cows available. The cow heights will be between 11 and NN. It is guaranteed the sum of NN over all test cases will not exceed 10610^6.

输出格式

(见题面原文)

数据范围

Inputs 2-3: T≤100,N≤7T\le 100, N \le 7 Inputs 4-5: T≤104T \le 10^4, all cows will have height at most 10. Inputs 6-11: No additional constraints. Problem credits: Nick Wu

样例

样例 1

2
4
1 1 2 3
4
3 3 2 1
3
1
For the first test case, FJ can take the cows with heights $1$, $1$, and $3$,
and rearrange them into $[1,3,1]$, which satisfies all the conditions. For the
second test case, FJ can take the cow with height $3$ and form a valid photo.