레이팅 미적용설명
일렬로 놓인 \(N\)개의 돌 무더기가 있다. \(i\)번째 무더기에는 돌이 \(a_i\)개 있다.
인접한 두 무더기를 골라 하나로 합칠 수 있으며, 이때 두 무더기의 돌 개수 합만큼 비용이 든다. 모든 무더기를 하나로 합칠 때까지 반복할 때, 비용 합의 최솟값을 구하여라.
이 버전에서는 구간 동적 계획법의 단순한 \(O(N^3)\) 풀이가 통과할 수 없다. 최적 분할점의 단조성을 증명하고 Knuth Optimization을 적용해야 한다.
제약
\(1 \le N \le 4{,}000\)
\(1 \le a_i \le 10{,}000\)
입력 형식
첫 줄에 무더기의 수 \(N\)이 주어진다.
둘째 줄에 \(a_1, \dots, a_N\)이 주어진다.
출력 형식
비용 합의 최솟값을 한 줄에 출력한다.
예제 1
입력
4
40 30 30 50
출력
300설명
(30,30)을 합쳐 60(비용 60), (40,60)을 합쳐 100(비용 100), (100,50)을 합쳐 150(비용 150). 총 비용은 310으로 최소이다.
예제 2
입력
1
7
출력
0설명
무더기가 하나뿐이므로 합칠 필요가 없어 비용은 0이다.
문제 정보
riseoj 작성
출처 Original
태그