제곱 비용 정확히 K분할
다이아몬드 III의견: 0
\(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\)개의 그룹으로 나눌 때 전체 비용의 최솟값을 한 줄에 출력한다.
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이다.
4 4
1 2 3 4
304개를 4그룹이면 각 원소가 한 그룹. 비용 \(1+4+9+16=30\).
riseoj 작성
출처 Original
평가 및 의견
제곱 비용 정확히 K분할
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
제곱 비용 정확히 K분할