BOJ. Merge Files (11066)

Problem

The cost of merging two adjacent files is the sum of their sizes. After every merge, the result remains in the same sequence, so an optimal plan can be split at its final merge: the files in [i, k] are merged first, the files in [k + 1, j] are merged separately, and those two results are merged for a cost equal to the total size of [i, j].

Let dp[i][j] be the minimum cost to merge files i through j (zero-based, inclusive), and let prefix contain prefix sums of file sizes. Then:

dp[i][i] = 0
dp[i][j] = prefix[j + 1] - prefix[i]
           + min(dp[i][k] + dp[k + 1][j]), i <= k < j

The interval sum is computed in constant time from the prefix sums. A direct search over every split takes O(K^3) time. Here each file size is positive, so the interval-sum cost satisfies the quadrangle inequality and is monotone with interval inclusion. The resulting optimal split points satisfy the Knuth monotonicity invariant:

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

Therefore, when computing dp[i][j], it is sufficient to inspect split points from opt[i][j - 1] through opt[i + 1][j], inclusive, rather than the full interval. Initialize opt[i][i] = i; process intervals in increasing length so both neighboring optima have already been computed. Selecting the first minimum in each interval gives a consistent opt table. This reduces the total running time to O(K^2), with O(K^2) space for dp and opt (and O(K) for prefix sums). long is used for all costs and prefix sums.

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int testCases = input.nextInt();
        StringBuilder output = new StringBuilder();

        while (testCases-- > 0) {
            int k = input.nextInt();
            long[] prefix = new long[k + 1];
            for (int i = 0; i < k; i++) {
                prefix[i + 1] = prefix[i] + input.nextInt();
            }

            long[][] dp = new long[k][k];
            int[][] opt = new int[k][k];
            for (int i = 0; i < k; i++) {
                opt[i][i] = i;
            }

            for (int length = 2; length <= k; length++) {
                for (int i = 0; i + length <= k; i++) {
                    int j = i + length - 1;
                    int firstSplit = opt[i][j - 1];
                    int lastSplit = opt[i + 1][j];
                    long intervalSize = prefix[j + 1] - prefix[i];
                    long best = Long.MAX_VALUE;
                    int bestSplit = firstSplit;

                    for (int split = firstSplit; split <= lastSplit; split++) {
                        long cost = dp[i][split] + dp[split + 1][j] + intervalSize;
                        if (cost < best) {
                            best = cost;
                            bestSplit = split;
                        }
                    }
                    dp[i][j] = best;
                    opt[i][j] = bestSplit;
                }
            }

            output.append(dp[0][k - 1]).append('\n');
        }

        System.out.print(output);
    }

    private static final class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int length;
        private int position;

        private int read() throws IOException {
            if (position == length) {
                length = input.read(buffer);
                position = 0;
                if (length == -1) return -1;
            }
            return buffer[position++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return value;
        }
    }
}