11066번: 파일 합치기

https://www.acmicpc.net/problem/11066


p[i]: i번째 파일 크기

$O(n^3)$

dp[i][j]: p[i...j]를 합칠때 드는 최소 비용
dp[i][j]=min(dp[i][k]+dp[k+1][j])+sum(p[i...j])

#include<cstdio>
int t, n, s[501], dp[501][501];
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", s + i), s[i] += s[i - 1];
        for (int i = 2; i <= n; i++) {
            for (int j = i; --j;) {
                dp[j][i] = 2e9;
                for (int k = j; k <= i; k++)
                    if (dp[j][i] > dp[j][k] + dp[k + 1][i]) dp[j][i] = dp[j][k] + dp[k + 1][i];
                dp[j][i] += s[i] - s[j - 1];
            }
        }
        printf("%d\n", dp[1][n]);
    }
    return 0;
}

$O(n^2)$

a<=b<=c<=d인 a,b,c,d에 대해
1) sum(p[a...c])+sum(p[b...d])<=sum(p[b...c])+sum(p[a...d])
2) sum(p[b...c])<=sum(p[a...d])
이므로 knuth optimization을 적용할 수 있다.

dp[i][j]: p[i+1...j]를 합칠 때 드는 최소 비용
opt[i][j]: dp[i][j]를 구할 때 사용한 최적 k

#include<cstdio>
int t, n, dp[501][501], opt[501][501], s[501];
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", s + i);
            s[i] += s[i - 1];
            opt[i - 1][i] = i;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j + i <= n; j++) {
                dp[j][j + i] = 2e9;
                for (int k = opt[j][j + i - 1]; k <= opt[j + 1][j + i]; k++) {
                    if (dp[j][j + i]>dp[j][k] + dp[k][j + i]) {
                        dp[j][j + i] = dp[j][k] + dp[k][j + i];
                        opt[j][j + i] = k;
                    }
                }
                dp[j][j + i] += s[j + i] - s[j];
            }
        }
        printf("%d\n", dp[0][n]);
    }
    return 0;
}