Editorial for Merge Piles

Approach

The important observation is that after several moves, every group always contains a contiguous range of the original piles.

Let $dp_{l,r}$ be the minimum cost needed to merge piles $l, l + 1, \ldots, r$ into one group. If $l = r$, the range is already one group, so $dp_{l,r} = 0$.

For a range with at least two piles, consider the final merge made inside that range. Immediately before that final merge, the range must be split into two adjacent merged groups: $l, \ldots, k$ and $k + 1, \ldots, r$ for some $l \le k < r$.

The cost is:

$dp_{l,k} + dp_{k+1,r} + a_l + a_{l+1} + \cdots + a_r$

Try every possible split $k$ and take the minimum. Prefix sums let us find each range sum in constant time.

Compute the values in increasing order of interval length, since shorter intervals are needed before longer intervals.

Time complexity is $O(N^3)$.

Solution (Python)

import sys

data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
a = data[1:]

prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + a[i]

dp = [[0] * n for _ in range(n)]

for length in range(2, n + 1):
    for left in range(n - length + 1):
        right = left + length - 1
        total = prefix[right + 1] - prefix[left]
        best = 10**30

        for split in range(left, right):
            cost = dp[left][split] + dp[split + 1][right] + total
            if cost < best:
                best = cost

        dp[left][right] = best

print(dp[0][n - 1])