题解 | #凸多边形的划分#

__int128

#define int long long
using namespace std;
template <class T> inline void read(T& x) { x = 0; char c = getchar(); bool f = 0; for (; !isdigit(c); c = getchar()) f ^= (c == '-'); for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48); x = f ? -x : x; }
template <class T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x < 10) putchar(x + 48); else write(x / 10), putchar(x % 10 + 48); }
const int N = 3e5+4;

int n;
inline void sol(){
	read(n);
	vector<__int128> a(n+1,0);
	for(int i=1;i<=n;i++) read(a[i]);
	//选点来考虑会比较抽象，我们考虑怎么选边来考虑，因为我们选中一条定边后，剩下要做的事就是找出三角形剩下的那个点，从而确定图形 
	//设f[i][j] 顶点i~顶点j三角剖分后的max乘积 
	//现在i到j这条边选上，然后考虑i~j中的某一个顶点作为第三个点
	//则有 f[i][j] = min(f[i][k] + f[k][j] + a[i]*a[j]*a[k]
	//最后我们选定1,n连接的边（跨数组）来定结果 答案即f[1][n] 
	vector<vector<__int128>> f(n+1,vector<__int128>(n+1,0));
	for(int len = 3; len <= n; len++){
		for(int l = 1; ; l++){
			int r = l + len - 1;
			if(r > n) break;
			f[l][r] = 1e30;
			for(int k = l + 1; k < r; k++)
				f[l][r] = min(f[l][r],f[l][k] + f[k][r] + a[l]*a[r]*a[k]);
		}
	}
	write(f[1][n]), putchar('\n');
}

signed main(){
	int ttt= 1;
	while(ttt--) sol();
	return 0;
}