题解

题意分析
正 n 边形顶点顺时针排列，选出若干互不重叠（内部无交）、顶点互不重复的三角形，每个三角形贡献 (a_i a_j a_k)，求总和最大值。
关键几何结论：凸多边形内部不重叠、顶点不共用的三角形等价于将一段连续顶点区间划分成若干三元组三角形，区间之间互不交叉。
转化为区间 DP：设 (dp[l][r]) 表示顶点区间 ([l,r]) 能选出合法三角形的最大得分。
合法区间长度：只有区间顶点数量 (\ge3) 才能构成三角形，且要选出不重叠三角形，区间长度 (len=r-l+1) 必须满足 (len \mod 3 =0) 才有完整划分；否则只能选部分。
转移思路：

区间 ([l,r]) 若不选任何三角形：(dp[l][r]=0)
若取一个三角形 ((l,m,r))（(l,m,r) 三点构成一个三角形，把区间拆成 ([l+1,m-1]) 和 ([m+1,r-1]) 两个独立子区间），则：
(dp[l][r] = \max_{l<m<r} \big(dp[l+1][m-1] + dp[m+1][r-1] + a_l a_m a_r\big))
区间拆分：(dp[l][r]=\max(dp[l][r], dp[l][k]+dp[k+1][r]))，枚举中间分割点 k，左右区间独立选三角形。

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 405;
ll dp[MAXN][MAXN];
int a[MAXN];
int n;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    memset(dp, 0, sizeof(dp));
    // 区间长度 len 从小到大 DP
    for (int len = 3; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            // 方案1：选三角形 l,m,r
            for (int m = l + 1; m < r; ++m) {
                ll cur = dp[l+1][m-1] + dp[m+1][r-1] + 1LL * a[l] * a[m] * a[r];
                dp[l][r] = max(dp[l][r], cur);
            }
            // 方案2：分割为左右两段
            for (int k = l; k < r; ++k) {
                dp[l][r] = max(dp[l][r], dp[l][k] + dp[k+1][r]);
            }
        }
    }
    cout << dp[1][n] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

复杂度说明
DP 状态数：(O(n^2))
每个状态 ([l,r]) 两层枚举 m、k，单次 (O(n))，总复杂度 (O(n^3))
题目限制所有测试用例 (n^3) 之和 (\le 400^3)，完全通过时限。
样例验证输入第一组：
3
1 2 3
(dp[1][3] = 1\times2\times3=6)，输出 6，与样例一致。第二组 (n=4,a=[2,1,3,4])
最优选三角形 ((1,3,4):2\times3\times4=24)，输出 24，匹配样例。核心思路解释
几何转区间 DP：凸多边形不重叠、顶点不共用的三角形只能由连续区间拆分得到，任意三个顶点构成三角形会把区间分割为左右两段独立子区间，互不干扰。
两种转移

以 (l,r) 为三角形两个端点，中间选 m 构成一个三角形，加上内部两段区间最优解；
将区间切分成左右两块，分别求最优相加。

数据类型：(a_i\le1000)，三元乘积最大 (10^9)，多个累加会爆 int，必须用 long long。

跑路了