문제
Bessie는 휴대폰으로 게임을 다운받아 하는 걸 좋아하지만, 커다란 발굽 때문에 작은 터치스크린을 다루는 데에는 약간 불편함을 느낍니다.
지금 Bessie가 하는 게임은 다음과 같습니다. 게임은 먼저 길이가 N인 양의 정수 수열로 시작합니다.
여기서 N은 2 ≤ N ≤ 248 이고, 각 원소는 1 이상 40 이하의 정수입니다.
한 번의 이동에서 Bessie는 값이 같은 인접한 두 수를 골라, 그것들을 값이 1 더 큰 하나의 수로 교체할 수 있습니다.
예를 들어, 인접한 두 개의 7을 골라 8 하나로 바꿀 수 있습니다.
게임의 목표는, 이런 연산들을 적절히 수행하여 게임이 끝났을 때 수열 안에 존재하는 수들 중 최댓값을 가능한 한 크게 만드는 것입니다.
Bessie가 만들 수 있는 가장 큰 수의 값을 구해 주세요.
입력
첫 번째 줄에 정수 N이 주어집니다.
다음 N개의 줄에는 게임 시작 시 수열을 이루는 N개의 정수가 한 줄에 하나씩 주어집니다.
출력
Bessie가 만들 수 있는 정수의 최댓값을 출력합니다.
예제
4
1
1
1
2
3
처음 수열은 1 1 1 2 입니다.
Bessie는 먼저 두 번째와 세 번째 1을 합쳐 1 2 2 를 만들 수 있습니다.
그 다음, 두 개의 2를 합쳐 3을 만들면 최종 수열은 1 3 이 되고, 이때 최댓값은 3입니다.
주의: 처음에 첫 번째와 두 번째 1을 합쳐 2 1 2 를 만드는 선택은 최적이 아닙니다.
출처
USACO 2016 US Open Gold
로그인해야 코드를 작성할 수 있어요.