8076 : K 그룹 최소 비용 분할
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 원소로 이루어진 수열이 주어집니다.
이 수열을 정확히 $K$개의 연속된 그룹으로 분할할 때, 각 그룹의 합을 더한 값의 최솟값을 구하는 프로그램을 작성하십시오.
각 그룹은 반드시 1개 이상의 원소를 포함해야 합니다.
[제약 조건]
• $1 \le K \le N \le 3{,}000$
• $1 \le A_i \le 1{,}000$
이 수열을 정확히 $K$개의 연속된 그룹으로 분할할 때, 각 그룹의 합을 더한 값의 최솟값을 구하는 프로그램을 작성하십시오.
각 그룹은 반드시 1개 이상의 원소를 포함해야 합니다.
[제약 조건]
• $1 \le K \le N \le 3{,}000$
• $1 \le A_i \le 1{,}000$
입력 설명
첫째 줄에 수열의 길이 $N$과 그룹의 수 $K$가 공백으로 구분되어 주어집니다. ($K \le N \le 3{,}000$, $1 \le K \le N$)
둘째 줄에 수열을 구성하는 $N$개의 양의 정수가 공백으로 구분되어 주어집니다. ($1 \le A_i \le 1{,}000$)
둘째 줄에 수열을 구성하는 $N$개의 양의 정수가 공백으로 구분되어 주어집니다. ($1 \le A_i \le 1{,}000$)
출력 설명
수열을 $K$개의 연속된 그룹으로 분할할 때 각 그룹의 합의 합계 최솟값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3
1 3 2 4 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
11도움
$dp[t][i]$를 앞의 $i$개의 원소를 정확히 $t$개의 그룹으로 분할하는 최솟값으로 정의하고 점화식 $dp[t][i] = \min_{j < i}(dp[t-1][j] + cost(j+1, i))$를 적용합니다.
분할 정복 DP 최적화(Divide and Conquer DP Optimization)를 적용하면 $O(KN \log N)$으로 해결 가능하며, 일반 DP는 $O(KN^2)$입니다.
분할 정복 DP 최적화(Divide and Conquer DP Optimization)를 적용하면 $O(KN \log N)$으로 해결 가능하며, 일반 DP는 $O(KN^2)$입니다.