Overview

This problem asks for the minimum cost of merging stone tablets arranged in a circle by combining adjacent pairs one at a time.
The essence is “interval merge DP (optimal binary tree-type DP),” and the circular arrangement can be handled by doubling the array and exhaustively searching over all “contiguous intervals of length \(N\).”

Analysis

First, considering the same problem on a line, the minimum cost to merge the interval \([l,r]\) into one can be expressed by:

• Where the interval was last split into two sub-intervals (split point \(k\))
• The cost to merge the left and right parts
• The cost of the final merge of left and right (interval sum)

This is a classic interval DP.

Why the naive approach doesn’t work

• The number of merging orders explodes on the order of Catalan numbers, making brute-force search impossible.
• Even with standard interval DP,
  \(dp[l][r] = \min_{l \le k < r}(dp[l][k]+dp[k+1][r]+\text{sum}(l,r))\)
  directly computed gives \(O(N^3)\).
• Since this problem involves a circle, even after simplification, \(O(N^3)\) is too heavy for \(N=1000\).

How to handle the circular arrangement

Since the circle simply means the starting position is not fixed, we double the array:
\(B = A + A\)
and consider all “contiguous intervals of length \(N\)”: \([s, s+N-1]\).
By solving each candidate interval as a linear problem and taking the minimum, we obtain the answer for the circle.

Key point for optimization

This DP has a form where Knuth’s optimization can be applied.
If we let opt[l][r] be the optimal split point, the following holds:

\(opt[l][r-1] \le opt[l][r] \le opt[l+1][r]\)

This narrows the search range for the split point, reducing the overall complexity to \(O(N^2)\).
The submitted code uses this monotonicity to shorten the loop over k.

Algorithm

1. Double the input array A to create B = A + A (length 2N).
2. Build a prefix sum array pref to retrieve interval sums in \(O(1)\).
3. DP definition:
   • dp[l][r]: minimum cost to merge B[l..r] into one tablet
   • opt[l][r]: the optimal split point for that
4. Initial values:
   • Intervals of length 1 have cost 0 (already a single tablet)
   • opt[i][i] = i
5. Update in order of interval length length = 2..N:
   • total = sum(l,r)
   • Restrict the search range to
     left = opt[l][r-1], right = opt[l+1][r]
     (clipped to l..r-1 if necessary)
   • Try k from left..right and adopt the minimum of
     dp[l][k] + dp[k+1][r] + total
6. Finally, for all starting positions s=0..N-1,
   take the minimum of dp[s][s+N-1] as the answer.

Complexity

• Time complexity: \(O(N^2)\) (interval DP with Knuth’s optimization)
• Space complexity: \(O(N^2)\) (dp and opt are both \(2N \times 2N\))

Implementation Notes

• Costs can become extremely large, so use a sufficiently large value like INF = 10**30.

• Do not recompute interval sums each time; always retrieve them in \(O(1)\) using the prefix sum array.

• Although opt ranges are theoretically monotone, in implementation it is important to clip with l and r-1 to prevent out-of-bounds or invalid range access.

  Source Code

import sys


def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))

    B = A + A
    pref = [0] * (2 * N + 1)
    for i in range(2 * N):
        pref[i + 1] = pref[i] + B[i]

    INF = 10**30
    M = 2 * N

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

    for i in range(M):
        opt[i][i] = i

    for length in range(2, N + 1):
        for l in range(0, M - length + 1):
            r = l + length - 1
            total = pref[r + 1] - pref[l]

            left = opt[l][r - 1]
            right = opt[l + 1][r]
            if left < l:
                left = l
            if right > r - 1:
                right = r - 1

            best = INF
            bestk = left
            for k in range(left, right + 1):
                v = dp[l][k] + dp[k + 1][r] + total
                if v < best:
                    best = v
                    bestk = k

            dp[l][r] = best
            opt[l][r] = bestk

    ans = INF
    for s in range(N):
        ans = min(ans, dp[s][s + N - 1])

    print(ans)


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.