레이팅 미적용설명
일렬로 놓인 \(N\)개의 돌 무더기가 있다. \(i\)번째 무더기에는 돌이 \(a_i\)개 있다.
인접한 두 무더기를 골라 하나로 합칠 수 있으며, 이때 두 무더기의 돌 개수 합만큼 비용이 든다. 모든 무더기를 하나로 합칠 때까지 반복할 때, 비용 합의 최솟값을 구하여라.
이 버전은 구간의 길이가 짧은 순서대로 계산하는 \(O(N^3)\) 구간 동적 계획법으로 해결할 수 있다.
제약
\(1 \le N \le 400\)
\(1 \le a_i \le 10{,}000\)
입력 형식
첫 줄에 무더기의 수 \(N\)이 주어진다.
둘째 줄에 \(a_1, \dots, a_N\)이 주어진다.
출력 형식
비용 합의 최솟값을 한 줄에 출력한다.
예제 1
입력
4
40 30 30 50
출력
300
예제 2
입력
1
7
출력
0
문제 정보
riseoj 작성
출처 Original
태그