Energy beads on a circcular necklace each have a head and tail marker, both positive integers. Adjacent beads satisfy that the tail of one equals the head of the next. Merging two adjacent beads with head a, tail b and head b, tail c releases energy a * b * c, producing a new bead with head a and tail c. The goal is to determine the merge order that maximizes total energy release until one bead remains.

Given n beads, with head markers provided, the tail of bead i equals the head of bead i+1 for i<n, and the tail of bead n equals the head of bead 1. The input specifies n and the head markers in clockwise order.

To handle the circular structure, duplicate the sequence to length 2n. Define dp[i][j] as the maximum energy from merging beads in the interval [i, j] into one bead. The recurrence is:

for (int len = 2; len <= n; ++len) {
    for (int start = 1; start + len - 1 < 2 * n; ++start) {
        int end = start + len - 1;
        for (int split = start; split < end; ++split) {
            dp[start][end] = max(dp[start][end],
                                 dp[start][split] + dp[split + 1][end] +
                                 head[start] * head[split + 1] * head[end + 1]);
        }
    }
}

Here, head stores the head markers, with indices from 1 to 2n. The energy from merging two subintervals uses the head markers at positions start, split+1, and end+1.

After copmutation, the answer is the maximum dp[i][i + n - 1] for 1 <= i <= n.

For example, with n=4 and head markers [2, 3, 5, 10], the optimal total energy is 710, achieved by merging in the order ((4⊕1)⊕2)⊕3.

Sample implementation in C++:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int beadCount;
    cin >> beadCount;
    vector<long long> markers(2 * beadCount + 2);
    for (int idx = 1; idx <= beadCount; ++idx) {
        cin >> markers[idx];
        markers[idx + beadCount] = markers[idx];
    }
    vector<vector<long long>> maxEnergy(2 * beadCount + 2, vector<long long>(2 * beadCount + 2, 0));
    for (int intervalLen = 2; intervalLen <= beadCount; ++intervalLen) {
        for (int left = 1; left + intervalLen - 1 < 2 * beadCount; ++left) {
            int right = left + intervalLen - 1;
            for (int mid = left; mid < right; ++mid) {
                long long mergeValue = markers[left] * markers[mid + 1] * markers[right + 1];
                maxEnergy[left][right] = max(maxEnergy[left][right],
                                             maxEnergy[left][mid] + maxEnergy[mid + 1][right] + mergeValue);
            }
        }
    }
    long long best = 0;
    for (int begin = 1; begin <= beadCount; ++begin) {
        best = max(best, maxEnergy[begin][begin + beadCount - 1]);
    }
    cout << best << endl;
    return 0;
}

Constraints: 4 ≤ n ≤ 100, markers ≤ 1000, and output ≤ 2.1×10^9.