레이팅 미적용오늘 소들은 유난히 장난기가 가득하다! 농부 존은 그저 소들이 한 줄로 서 있는 사진을 찍고 싶을 뿐이지만, 소들은 그가 셔터를 누르기 직전마다 계속 움직인다.
구체적으로, 농부 존의 소 \(N\)마리(\(1 \le N \le 10^5\))는 각각 \(1\)부터 \(N\)까지의 정수 키를 가진다. 농부 존은 소들이 아주 특정한 순서로 줄을 선 사진을 찍고 싶다. 왼쪽에서 오른쪽으로 줄을 섰을 때 소들의 키가 \(h_1, \dots, h_K\)라면, 소들의 키가 다음 세 가지 성질을 만족하기를 원한다.
- 소들의 키가 증가했다가 감소하기를 원한다. 형식적으로, \(h_1 \le \dots \le h_i \ge \dots \ge h_K\)를 만족하는 정수 \(i\)가 존재해야 한다.
- 어떤 소도 자신과 키가 정확히 같은 소 옆에 서 있지 않기를 원한다. 형식적으로, 모든 \(1 \le i < K\)에 대해 \(h_i \neq h_{i+1}\)이다.
- 사진이 대칭이기를 원한다. 형식적으로, \(i + j = K+1\)이면 \(h_i = h_j\)이다.
농부 존은 사진에 가능한 한 많은 소가 담기기를 원한다. 구체적으로, 농부 존은 일부 소를 제외하고 나머지 소들을 재배치할 수 있다. 조건을 만족하면서 사진에 담을 수 있는 소의 최대 수를 계산하시오.
Problem credits: Nick Wu
배점
- 입력 2-3: \(T\le 100, N \le 7\)
- 입력 4-5: \(T \le 10^4\), 모든 소의 키가 10 이하이다.
- 입력 6-11: 추가 제약이 없다.
Problem credits: Nick Wu
여러 개의 테스트 케이스에 답해야 한다.
첫째 줄에 테스트 케이스의 수를 나타내는 정수 \(T\)(\(1 \leq T \leq 10^5\))가 주어진다. 이어서 \(T\)개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫째 줄에 정수 \(N\)이 주어진다. 각 테스트 케이스의 둘째 줄에 사용 가능한 소 \(N\)마리의 키를 나타내는 정수 \(N\)개가 주어진다. 소의 키는 \(1\) 이상 \(N\) 이하이다.
모든 테스트 케이스에 대한 \(N\)의 합은 \(10^6\)을 넘지 않음이 보장된다.
\(T\)개의 줄을 출력한다. \(i\)번째 줄에 \(i\)번째 테스트 케이스의 답을 출력한다. 각 줄은 농부 존이 사진에 담을 수 있는 소의 최대 수를 나타내는 정수여야 한다.
2
4
1 1 2 3
4
3 3 2 13
1For 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.
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > US Open > Bronze