레이팅 미적용소 베시는 카드 게임의 열렬한 팬이다. 마주 볼 수 있는 엄지손가락이 없다는 점을 생각하면 꽤 놀라운 일이다. 안타깝게도 무리의 다른 소들 중에는 좋은 상대가 없다. 사실 그들은 너무 못해서 항상 완전히 예측 가능한 방식으로 플레이한다! 그럼에도 베시가 이기는 방법을 알아내는 것은 여전히 도전이 될 수 있다.
베시와 친구 엘시는 지금 간단한 카드 게임을 하고 있다. \(1 \ldots 2N\)으로 번호가 붙은 \(2N\)장의 카드 덱을 베시에게 \(N\)장, 엘시에게 \(N\)장으로 나눈다. 그런 다음 두 소는 \(N\)번의 라운드를 진행하는데, 각 라운드마다 베시와 엘시가 카드를 한 장씩 낸다. 처음에는 더 높은 카드를 낸 쪽이 1점을 얻는다. 하지만 게임 도중 한 시점에 베시는 규칙을 바꾸기로 결정할 수 있으며, 그 이후로는 게임이 끝날 때까지 더 낮은 카드를 낸 쪽이 1점을 얻는다. 베시는 이 옵션을 사용하지 않고 게임 전체를 "높은 카드가 이기는" 방식으로 둘 수도 있고, 아예 시작하자마자 옵션을 발동해 게임 전체가 "낮은 카드가 이기는" 규칙을 따르게 할 수도 있다.
베시가 엘시가 카드를 낼 순서를 예측할 수 있다고 할 때, 베시가 얻을 수 있는 최대 점수를 구하시오.
Problem credits: Austin Bannister and Brian Dean
Problem credits: Austin Bannister and Brian Dean
입력의 첫째 줄에 N의 값(\(2 \leq N \leq 50,000\))이 주어진다.
다음 N개의 줄에는 엘시가 게임의 각 라운드에서 차례로 낼 카드가 주어진다. 이 정보로부터 베시의 카드를 쉽게 알아낼 수 있음에 유의하라.
베시가 얻을 수 있는 최대 점수를 한 줄에 출력한다.
cardgame.in · 출력을 쓸 파일 cardgame.out4
1
8
4
33Here, Bessie must have cards 2, 5, and 6, and 7 in her hand, and she can use
these to win at most 3 points. For example, she can defeat the 1 card and then
switch the rules to "low card wins", after which she can win two more rounds.
riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > December > Platinum