상자 묶기
플래티넘 I의견: 0
\(N\)개의 물건이 일렬로 놓여 있고 \(i\)번째 물건의 무게는 \(a_i\)이다. 이들을 정확히 \(K\)개의 연속한 묶음으로 나눈다. 각 묶음의 비용은 그 묶음에 속한 물건들 무게 합의 제곱이다.
즉 한 묶음의 물건 무게 합이 \(s\)이면 비용은 \(s^2\)이다. 모든 묶음의 비용 합을 최소로 하는 분할을 찾고 그 최소 비용을 구하여라.
\(O(K\ N^2)\) DP는 통과할 수 없다.
\(1 \le K \le N \le 50{,}000\)
\(1 \le a_i \le 10^4\)
첫 줄에 물건의 수 \(N\)과 묶음의 수 \(K\)가 주어진다.
둘째 줄에 \(N\)개의 무게 \(a_1, a_2, \dots, a_N\)이 공백으로 구분되어 주어진다.
모든 묶음의 비용 합의 최솟값을 출력한다.
5 2
3 1 4 1 5
100[3,1,4,1,5]를 2묶음으로. [3,1,4,1 | 5]: \(9^2+5^2=106\). [3,1,4 | 1,5]: \(8^2+6^2=100\). [3,1 | 4,1,5]: \(4^2+10^2=116\). 최소는 100이다.
3 3
10 10 10
3003개를 3묶음으로 나누면 각 묶음이 물건 하나씩. 비용은 \(10^2+10^2+10^2=300\).
riseoj 작성
출처 Original
평가 및 의견
상자 묶기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
상자 묶기