P1063 [NOIP 2006 提高组] 能量项链

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    // 断环成链：把头标记复制一遍，环就变成链
    vector<long long> a(2 * n + 3, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    a[2 * n + 1] = a[1]; // 环的尾部接回头部

    // f[i][j]：第 i..j 颗珠子合并成一颗时能释放的最大能量
    vector<vector<long long>> f(2 * n + 3, vector<long long>(2 * n + 3, 0));

    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= 2 * n; i++) {
            int j = i + len - 1;
            for (int k = i; k < j; k++) {
                // 最后一次合并：[i..k] 与 [k+1..j]，释放 a[i]*a[k+1]*a[j+1]
                long long energy = f[i][k] + f[k + 1][j] + a[i] * a[k + 1] * a[j + 1];
                f[i][j] = max(f[i][j], energy);
            }
        }
    }

    // 环上每种断开位置各算一次，取最大值
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, f[i][i + n - 1]);
    }

    cout << ans << "\n";
    return 0;
}