생산 라인 분할
플래티넘 III의견: 0
공장의 생산 라인에 \(N\)개의 작업이 일렬로 놓여 있다. \(i\)번째 작업의 부하는 \(a_i\)이다.
작업들을 앞에서부터 차례대로 정확히 \(K\)개의 연속한 구역으로 나누어 \(K\)명의 작업자에게 배정한다. 부하 합이 \(t\)이고 작업이 \(m\)개인 구역의 피로도는 \(m \cdot t\)이다.
피로도 합이 최소가 되도록 나눌 때 그 최솟값을 구하여라. 단순한 \(O(KN^2)\) 동적 계획법은 통과할 수 없으며, 최적 분할점의 단조성을 이용한 분할 정복 최적화가 필요하다.
\(1 \le N \le 50{,}000\)
\(1 \le K \le \min(N, 10)\)
\(1 \le a_i \le 10{,}000\)
첫 줄에 작업의 수 \(N\)과 구역의 수 \(K\)가 주어진다.
둘째 줄에 \(a_1, \dots, a_N\)이 주어진다.
피로도 합의 최솟값을 한 줄에 출력한다.
5 2
3 1 2 4 1
28[3,1,2]와 [4,1]로 나누면 피로도는 \(3 \cdot 6 + 2 \cdot 5 = 28\)로 최소이다.
3 3
5 5 5
15세 구역에 하나씩 배정하면 피로도는 \(1 \cdot 5\)씩 총 15이다.
riseoj 작성
출처 Original
평가 및 의견
생산 라인 분할
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
생산 라인 분할