The stone merging challenge involves arranging piles in a circular configuration and repeatedly combining adjacent groups until a single pile remains. Each merger generates a score equivalent to the total mass of the combined group. The algorithmic goal is to compute both the lowest and highest possible cumulative scores across all possible merge sequences.

Core Interval Dynamic Programming Concepts

Interval dynamic programming addresses problems where solutions for contiguous segments depend entirely on solutions of their sub-segments. The methodology partitions a target range into two disjoint subsections at a chosen pivot, solves both recursively or iteratively, and aggregates their results using a predefined weight function.

For linear arrangements, we define dp[i][j] as the optimal metric achievable by consolidating elements from index i to j. The transition formula evaluates every feasible cut location k:

dp[i][j] = op(dp[i][k], dp[k+1][j]) + w(i, j)

The operator op selects either the maximum or minimum aggregate, while w(i, j) denotes the immediate cost or benefit of joining the two halves. Computation follows a strict bottom-up progression based on segment length. By resolving shorter spans first, we guarantee that when a larger interval is processed, all required sub-interval values are already cached in memory.

Adapting Linear DP to Circular Structures

Circular boundaries break standard linear recurrence assumptions because the first and last elements interact directly. A standard workaround duplicates the original dataset, creating a linear sequence of double the initial length. This expansion covers every rotational permutation without requiring modular arithmetic during index traversal.

Once the full table is populated, the final result is derived by scanning all valid windows of the original length n. Specifically, we evaluate dp[i][i+n-1] for each valid starting position i and apply the appropriate extremum operator. This transformation preserves the baseline O(n³) time complexity while elegantly sidestepping edge-case handling.

C++ Implementation Strategy

The following implementation separates minimum and maximum tracking into distinct matrices. Prefix summation is employed to calculate range weights in constant time. The iterative approach explicitly initializes single-element bases, expands lengths systematically, and prunes invalid boundaries during the inner partition loop.

#include <algorithm>
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

const int LIMIT = 205;
const int INF = 1e9;

// Dedicated tables for divergent outcome tracking
int min_matrix[LIMIT][LIMIT];
int max_matrix[LIMIT][LIMIT];
int stones[LIMIT];
int prefix[LIMIT];

void build_prefix_array(int capacity) {
    prefix[0] = 0;
    for (int idx = 1; idx <= capacity; ++idx) {
        prefix[idx] = prefix[idx - 1] + stones[idx];
    }
}

inline int query_window(int left, int right) {
    return prefix[right] - prefix[left - 1];
}

int main() {
    int n;
    if (!(cin >> n)) return 0;

    // Mirror input to simulate cyclic adjacency
    for (int i = 1; i <= n; ++i) {
        cin >> stones[i];
        stones[i + n] = stones[i];
    }

    build_prefix_array(2 * n);

    // Base configuration: zero cost for singleton groups
    for (int i = 1; i <= 2 * n; ++i) {
        min_matrix[i][i] = 0;
        max_matrix[i][i] = 0;
    }

    // Expand progressively across increasing segment sizes
    for (int span = 2; span <= n; ++span) {
        for (int start = 1; start <= 2 * n - span + 1; ++start) {
            int finish = start + span - 1;
            min_matrix[start][finish] = INF;
            max_matrix[start][finish] = 0;

            // Traverse all intermediate splitting positions
            for (int pivot = start; pivot < finish; ++pivot) {
                int merged_min = min_matrix[start][pivot] + min_matrix[pivot + 1][finish] + query_window(start, finish);
                int merged_max = max_matrix[start][pivot] + max_matrix[pivot + 1][finish] + query_window(start, finish);

                min_matrix[start][finish] = min(min_matrix[start][finish], merged_min);
                max_matrix[start][finish] = max(max_matrix[start][finish], merged_max);
            }
        }
    }

    // Scan rotated windows to identify global extremes
    int best_min = min_matrix[1][n];
    int best_max = max_matrix[1][n];

    for (int shift = 2; shift <= n; ++shift) {
        best_min = min(best_min, min_matrix[shift][shift + n - 1]);
        best_max = max(best_max, max_matrix[shift][shift + n - 1]);
    }

    cout << best_min << '\n' << best_max << '\n';
    return 0;
}

The nested iteration hierarchy enforces the necessary evaluation order. By fixing the segment length before advancing the start coordinate, the algorithm prevents forward-reference errors. Array replication removes conditional modulo operations during boundary checks, streamlining execution and reducing branchign mispredictions in CPU pipelines.