일렬로 놓인 \(N\) 개의 울타리 조각이 있고, \(i\) 번째 조각의 길이는 \(a_i\) 입니다. 서로 인접한 두 조각(또는 이미 이어 붙인 두 묶음)을 하나로 이어 붙일 수 있으며, 길이 \(x\) 묶음과 길이 \(y\) 묶음을 이어 붙이는 데 드는 비용은 \(x+y\) 입니다.

모든 조각을 하나의 울타리로 이어 붙일 때 드는 총비용의 최솟값을 구하세요. (조각의 순서는 바꿀 수 없습니다.)

전형적인 돌 합치기(구간 합치기) 문제로, 누적합을 이용한 \(O(N^3)\) 구간 DP로 해결합니다.

• \(1 \le N \le 300\)
• \(1 \le a_i \le 1000\)

첫 줄에 조각의 수 \(N\) 이 주어집니다.

둘째 줄에 \(N\) 개의 정수 \(a_1, \dots, a_N\) 이 주어집니다.

모든 조각을 이어 붙이는 최소 비용을 한 줄에 출력합니다.

riseoj 작성

출처 Original