다이아몬드 II설명
\(N\)개의 음이 아닌 정수로 이루어진 수열 \(a_1, a_2, \dots, a_N\)이 있다. 이 수열을 정확히 \(K\)개의 연속한(비어 있지 않은) 그룹으로 나누려고 한다.
각 그룹의 비용은 그 그룹에 속한 수들의 합의 제곱이다. 전체 비용은 모든 그룹 비용의 합이다.
전체 비용의 최솟값을 구하여라.
\(N\)과 \(K\)가 크므로 \(O(KN^2)\) DP는 통과할 수 없다.
제약
\(1 \le K \le N \le 100{,}000\)
\(0 \le a_i \le 10^6\)
입력 형식
첫 줄에 수열의 길이 \(N\)과 그룹 수 \(K\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, \dots, a_N\)이 공백으로 구분되어 주어진다.
출력 형식
정확히 \(K\)개의 그룹으로 나눌 때 전체 비용의 최솟값을 한 줄에 출력한다.
예제 1
입력
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이다.
예제 2
입력
4 4
1 2 3 4
출력
30설명
4개를 4그룹이면 각 원소가 한 그룹. 비용 \(1+4+9+16=30\).
문제 정보
riseoj 작성
출처 Original
태그
