Placeholder

#5322

응답하라 262144 (262144 Revisited) 2초 256MB

문제

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


역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.