这篇题解告诉你怎么想

先看题，我相信没有人读不懂题，所以跳过解释。
注意到题中有一句话：“数据保证所有测试用例的 $n^3$ 之和不超过 $400^3$ 。”浅浅计算一下，发现 $400^3=6.4\times10^7$ ，刚好能通过。因此，可以明显看出，题目提醒我们使用单次时间复杂度为 $O( n^3 )$ 的算法做这道题。那么，请你仔细想一想，时间复杂度为 $O(n^3)$ 的算法有什么呢？反正我想了半天也就想到了飘忽不定的贪心、DP，以及Floyd。
很明显，这题和Floyd一点边都不沾，因此只能是贪心或DP。再请你仔细想一想，贪心和DP中的哪些经典类型的时间复杂度为 $O(n^3)$ 呢？反正我只能想到区间DP。
仔细读题发现有乘积，此时你就要警觉了：会不会爆int？浅浅算一下，发现 $1000\times1000\times1000\times400\div3\approx1.3\times10^{11}$ ，包炸的，因此一定要开long long。
然后就是去推区间DP的转移方程。我们画一个正……18边形（可能不够正，但是我只能画成这样了）。
其实我们并不需要真的去画一个正 $n$ 边形。因为我们知道正多边形的每一个顶点与这个多边形的几何中心一定都是相等的，因此我们可以通过一般推到特殊，直接画18个在一个圆上的点即可，如图。

我们随便取3个点，将它们构成的三角形画出来，如图二。

我们会发现，这三个点把整体18个点分成了3部分，即编号18+1至6，8至11，13至16。
我们先来看看如果所选的三个点在同一个部分里会发生什么。你可以自己试一试，就会发现，任何三个在同一部分内的点构成的三角形一定不与最初的三角形重叠。
我们再来看看如果所选的三个点不在同一部分里会发生什么。你也可以试一试，会发现这样的三个点构成的三角形一定与最初的三角形有重叠。
因此，我们可以得出，在选择了任意三个点后，再进行选择的三个点必须在同一个部分内。
所以，现在你应该可以清楚地看到一个区间DP的雏形了吧！
那么转移方程应该也很清楚了。在 $l$ 到 $r$ 的区间内，有两种转移：
第一种是在区间内选择一个非 $l$ 非 $r$ 的点 $m$ ，如果我们让 $l,r,m$ 构成三角形，那么此时 $l$ 到 $r$ 的区间的最大分数就是分成的在 $l$ 到 $r$ 的区间内的两个部分内部的最大分数加上新构成的三角形提供的分数。
第二种是取一个分界点 $k$ ， $k$ 分出的两个区间（其中一个一定要包含 $k$ ）的最大分数之和就是$l$ 到 $r$ 的区间的最大分数的一个预选值。
有的同学可能要问了：选择一个三角形之后，不应该会分出三个部分吗？为什么我们只加上了在 $l$ 到 $r$ 的区间内的两个部分呢？还有就是为什么要在区间内选择一个非 $l$ 非 $r$ 的点 $m$呢？其实是因为我们dp数组中$l$ 到 $r$ 的区间的最大分数只能包含在 $l$ 到 $r$ 的区间内的内容，因此不会加上外部内容。
还有一点优化，就是我们不需要处理区间大小<3的区间，因为那样的区间分数一定是0。初始化一下就好了。
另外要注意，由于题目有多组数据，因此一定要清空残留值。我的代码中为了节省时间，每次只清空了需要用的部分的残留值，你的代码自己定。
好了，该说的都说完了，上代码！
（我觉得不需要注释）

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define please return
#define AC 0;
using namespace std;
long long dp[440][440];
int a[440],t,n;
int main(){
//	freopen("data.in","r",stdin);
//	freopen("user.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			for(int j=1;j+2<=i;j++) dp[j][i]=0;
		}
		for(int k=3;k<=n;k++){
			for(int l=1;l+k-1<=n;l++){
				int r=l+k-1;
				for(int j=l+1;j<r;j++) dp[l][r]=max(dp[l][r],dp[l+1][j-1]+dp[j+1][r-1]+1ll*a[l]*a[r]*a[j]);
				for(int j=l;j<r;j++) dp[l][r]=max(dp[l][r],dp[l][j]+dp[j+1][r]);
			}
		}
		cout<<dp[1][n]<<'\n';
	}
	please AC
}

点个赞支持一下吧！