문제
Bessie는 휴대전화로 게임을 다운로드하는 것을 좋아하지만, 큰 발굽 때문에 작은 터치스크린을 사용하는 것이 번거롭다는 것을 알게 되었습니다.
그녀는 특히 그녀가 현재 하고 있는 게임에 매료되어 있습니다. 게임은 1~106 범위에 있는 N개의 양의 정수 수열 a1, a2, …, aN (2≤N≤262,144)로 시작합니다. 한 턴에 Bessie는 인접한 두 숫자를 가져와 두 숫자의 최대값보다 큰 숫자로 바꿀 수 있습니다(예: 인접한 숫자 쌍(5,7)을 8로 바꿀 수 있음). 게임은 N−1 턴후에 종료되며, 이 시점에서 남은 숫자는 하나뿐입니다. 게임의 목표는 이 최종 숫자를 최소화하는 것입니다.
베시는 이 게임이 당신에게 너무 쉽다는 것을 알고 있습니다. 따라서 귀하의 임무는 게임을 최적으로 플레이하는 것뿐만 아니라 의 연속적인 부분수열에서 게임을 플레이하는 것입니다.
a의 모든 N*(N+1)/2 개의 부분수열에서 나올 수 있는가능한 가장 작은 최종 값의 합계를 출력합니다.
입력
입력의 첫 번째 줄에는 N이 출력됩니다.
두 번째 줄에는 수열을 나타내는 N개의 공백으로 구분된 정수가 있습니다.
출력
합을 출력하시오.
예제1
6
1 3 1 2 1 10
115
총 6⋅7/2=21개의 연속적인 부분수열이 있습니다. 예를 들어, 연속적인 부분수열 [1,3,1,2,1]에 대해 가능한 가장 작은 최종 숫자는 5이며 다음 작업 순서로 도달할 수 있습니다.
초기값 -> [1,3,1,2,1]
1&3의 조합 -> [4,1,2,1]
2&1의 조합 -> [4,1,3]
1&3의 조합 -> [4,4]
4&4의 조합 -> [5]
다음은 각 연속적인 부분수열에 대해 가능한 가장 작은 최종 숫자입니다.
최종(1:1) = 1
최종(1:2) = 4
최종(1:3) = 5
최종(1:4) = 5
최종(1:5) = 5
최종(1:6) = 11
최종(2:2) = 3
최종(2:3) = 4
최종(2:4) = 4
최종(2:5) = 5
최종(2:6) = 11
최종(3:3) = 1
최종(3:4) = 3
최종(3:5) = 4
최종(3:6) = 11
최종(4:4) = 2
최종(4:5) = 3
최종(4:6) = 11
최종(5:5) = 1
최종(5:6) = 11
최종(6:6) = 10
출처
USACO 2022 US Open Platinum
로그인해야 코드를 작성할 수 있어요.