11066 파일합치기

1. 문제

2. 코드

#include <queue>
#include <iostream>
 
using namespace std;
 
int dp[501][501];
int num[501][501];
int cost[501];
int sum[501];
int T,K;
int d;
 
int main()
{
    for (scanf("%d", &T); T--;) {
        scanf("%d", &K);
        for (int i = 1; i <= K; i++)
            scanf("%d", &cost[i]), sum[i] = sum[i - 1] + cost[i];
        for (int i = 1; i <= K; i++)
            num[i - 1][i] = i;
 
        for (d = 2; d <= K; d++) {
            for (int i = 0; i+d <= K; i++) {
                int j = i + d;
                dp[i][j] = 2e9;
                for (int k = num[i][j - 1]; k <= num[i + 1][j]; k++) {
                    int v = dp[i][k] + dp[k][j] + sum[j] - sum[i];
                    if (dp[i][j] > v)
                        dp[i][j] = v, num[i][j] = k;
                }
            }
        }
        printf("%d\n", dp[0][K]);
    }
}

3. 후기

Kruth's optimization을 이용하여 최적화 시킬 수 있다. 

1) 사각부등식

C[a][c]+C[b][d]<=C[a][d]+C[b][c] (a<=b<=c<=d) 

2) 단조증가

C[b][c]<=C[a][d] (a<=b<=c<=d)

위 두 조건을 만족하는 C[][]에 대해,

점화식이 dp[i][j] = min(i < k < j){dp[i][k] + dp[k][j]} + C[i][j] 꼴이라 하자. 

이 때, num[i][j]란 dp[i][j]가 최소가 되게 하는 k(i < k < j)값을 저장하는 배열이라 정의하면, 다음이 성립한다.

num[i][j-1]  <= num[i][j] <= num[i+1][j]

출처 - https://js1jj2sk3.tistory.com/3