思路与算法

dp[l][r]为区间合体最大收益。枚举分离点k∈[l,r-1]，左右子区间收益相加，再加(a[l]+a[r])*a[k]。单区域不分离，收益0。记录最优k，遇到相同收益保留较小k。恢复时把整个区间入队，输出队首区间的分离点后，依次把左右子区间入队，直到只剩单区域。

正确性说明

第一次分离将问题分成相互独立的两个连续区间，最终这两个子区间合体时的额外收益仅由l,r,k决定。因而各子区间最优值可以相加，枚举k完整覆盖全部可能首次分离。按长度归纳dp最优。相同收益选较小首次分离点，使输出的第一个不同决策最小；子问题采用同样规则。队列按深度且从左到右处理，恰好实现题目要求的阶段输出顺序。

复杂度

时间O(n³)，空间O(n²)，包括收益表与决策表，初始化O(n²)。恢复阶段每节点入队一次O(n)，额外队列O(n)。n≤300，原题保证运算过程与结果在32位正整数内，程序仍用long long保存收益。

易错点

输出顺序是层序分离过程，不能用普通递归前序输出左右子问题。k最大r-1，不能分出空区间。相同收益只在严格更优时更新，保留最靠左决策。n=1时最大收益0，第二行为空。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    vector<vector<long long>> dp(n, vector<long long>(n));
    vector<vector<int>> cut(n, vector<int>(n));
    for (int len = 2; len <= n; ++len)
        for (int l = 0; l + len <= n; ++l) {
            int r = l + len - 1;
            for (int k = l; k < r; ++k) {
                long long value = dp[l][k] + dp[k + 1][r] + (a[l] + a[r]) * a[k];
                if (k == l || value > dp[l][r]) {
                    dp[l][r] = value;
                    cut[l][r] = k;
                }
            }
        }
    cout << dp[0][n - 1] << '\n';
    queue<pair<int, int>> q;
    q.push({0, n - 1});
    bool first = true;
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        int l = t.first, r = t.second;
        if (l == r)
            continue;
        int k = cut[l][r];
        if (!first)
            cout << ' ';
        first = false;
        cout << k + 1;
        q.push({l, k});
        q.push({k + 1, r});
    }
    cout << '\n';
}