Overview

The adjacent merge problem on a circular arrangement can be solved by cutting the circle at one position to make it a line.
The linear version can be solved with interval DP, but as-is it would be \(O(N^3)\), so we use Knuth’s optimization to speed it up to \(O(N^2)\).

Analysis

First, consider the case where stone slabs are arranged on a straight line instead of a circle.

1. Interval DP for the Linear Version

Let the minimum cost to merge all stone slabs in the interval \([l, r]\) into one slab be

\[ dp[l][r] \]

If the interval \([l, r]\) is finally split into two parts and merged, then using some \(k\):

• Merge the left part \([l, k]\) into one slab
• Merge the right part \([k+1, r]\) into one slab
• Finally merge those two slabs together

The cost of the final merge is the total weight of the entire interval \([l, r]\).
Therefore, the transition is

\[ dp[l][r] = \min_{l \le k < r} \left( dp[l][k] + dp[k+1][r] \right) + \sum_{i=l}^{r} A_i \]

This is a classic interval DP commonly seen in problems like “slime merging.”

---

2. How to Handle the Circular Arrangement

With a circular arrangement, it’s difficult to handle because there’s no fixed start and end point.
Here is the key insight:

Even in the optimal merging strategy for the circle, if we cut at one position, it can be viewed as a linear merging problem.

This is because in the final merge, the entire circle must have been divided into two contiguous intervals, and we can cut the circle at that boundary.

In other words, the answer for the circular case is:

• Cut the circle at some position
• Find the minimum cost as a linear problem
• Take the minimum over all possible cuts

---

3. Doubling the Array to Represent “All Possible Cuts”

To avoid the hassle of naively trying all cuts of the circle, we concatenate the array twice.

\[ B = A + A \]

For example, if

\[ A = [a_1, a_2, a_3, a_4] \]

then

\[ B = [a_1, a_2, a_3, a_4, a_1, a_2, a_3, a_4] \]

In this case, a contiguous interval of length \(N\)

\[ B[i], B[i+1], \dots, B[i+N-1] \]

corresponds exactly to “cutting the circle at a certain position to form a line.”
Therefore, the answer is

\[ \min_{0 \le i < N} dp[i][i+N-1] \]

---

4. The Naive Solution Is Too Slow

If we directly apply the linear interval DP:

• The number of intervals is \(O(N^2)\)
• For each interval, we exhaustively search the split point \(k\) in \(O(N)\)

So the total complexity is

\[ O(N^3) \]

Since \(N \le 3000\) in this problem, \(O(N^3)\) is too slow.

---

5. Speeding Up to \(O(N^2)\) with Knuth’s Optimization

This DP has the form

\[ dp[l][r] = \min_{l \le k < r} \left( dp[l][k] + dp[k+1][r] \right) + w(l, r) \]

where

\[ w(l,r)=\sum_{i=l}^r B_i \]

For this type of DP that “adds an interval sum,” Knuth’s optimization can be applied.
Let the split point that achieves the minimum be

\[ opt[l][r] \]

Then the following monotonicity holds:

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

In other words, the optimal split point for interval \([l,r]\) lies between the optimal split points of the adjacent intervals, so we don’t need to try all \(k\) each time.

By narrowing the search range to

\[ k = opt[l][r-1] \dots opt[l+1][r] \]

the overall complexity becomes \(O(N^2)\).

This is the essence of this problem.

Algorithm

1. Concatenate array \(A\) twice to create \(B=A+A\).
2. Create a prefix sum array prefix to compute interval sums in \(O(1)\).
3. Let dp[l][r] be “the minimum cost to merge \(B[l..r]\) into one slab.”
4. Let opt[l][r] be the optimal split point at that time.
5. Intervals of length 1 are already one slab, so $\( dp[i][i]=0 \)$
6. Fill in the DP by increasing the interval length from 2 to \(N\).
   • Interval sum $\( total = prefix[r+1]-prefix[l] \)$
   • By Knuth’s optimization, we only need to try split points $\( k \in [opt[l][r-1],\ opt[l+1][r]] \)$
   • Transition $\( dp[l][r] = \min_k \left(dp[l][k]+dp[k+1][r]+total\right) \)$
7. Finally, output the minimum over all intervals of length \(N\): $\( \min_{0 \le i < N} dp[i][i+N-1] \)$

Complexity

• Time complexity: \(O(N^2)\)
• Space complexity: \(O(N^2)\)

Implementation Notes

• Prefix sums are used to compute interval sums in \(O(1)\).
• The array is doubled to handle the circular arrangement.
• Since the DP only uses intervals up to length \(N\), it suffices to iterate length from 2 to N only.
• Costs can become very large, so when implementing in C++ or similar languages, long long is necessary.
• The search range for opt[l][r] is:
  • Left bound: opt[l][r-1]
  • Right bound: opt[l+1][r]

Be careful not to exceed r-1.

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    N = data[0]
    A = data[1:1 + N]

    B = A * 2
    M = 2 * N

    prefix = [0] * (M + 1)
    for i, x in enumerate(B):
        prefix[i + 1] = prefix[i] + x

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

    INF = 10**30

    for length in range(2, N + 1):
        for l in range(0, M - length + 1):
            r = l + length - 1
            left = opt[l][r - 1]
            right = opt[l + 1][r]
            if right > r - 1:
                right = r - 1

            total = prefix[r + 1] - prefix[l]
            row_l = dp[l]

            best = INF
            best_k = left
            for k in range(left, right + 1):
                cost = row_l[k] + dp[k + 1][r] + total
                if cost < best:
                    best = cost
                    best_k = k

            row_l[r] = best
            opt[l][r] = best_k

    ans = min(dp[i][i + N - 1] for i in range(N))
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.