You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
55 lines
1.2 KiB
55 lines
1.2 KiB
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
|
|
const int N = 50 + 10;
|
|
|
|
//__int128专用
|
|
typedef __int128 LL;
|
|
const LL INF = 1e38;
|
|
LL read() { // 快读
|
|
LL x = 0, f = 1;
|
|
char ch = getchar();
|
|
while (ch < '0' || ch > '9') {
|
|
if (ch == '-') f = -1;
|
|
ch = getchar();
|
|
}
|
|
while (ch >= '0' && ch <= '9') {
|
|
x = x * 10 + ch - '0';
|
|
ch = getchar();
|
|
}
|
|
return x * f;
|
|
}
|
|
void write(LL x) { // 快写
|
|
if (x < 0) putchar('-'), x = -x;
|
|
if (x > 9) write(x / 10);
|
|
putchar(x % 10 + '0');
|
|
}
|
|
|
|
LL w[N];
|
|
LL f[N][N];
|
|
|
|
// 计算[l,r]之间的三角剖分最大值
|
|
LL dfs(int l, int r) {
|
|
LL &v = f[l][r];
|
|
if (v != INF) return v; // 记忆化
|
|
if (r - l < 2) return v = 0; // 不够三个点，哪来的剖分值
|
|
for (int k = l + 1; k < r; k++) // 中间点k不能与l,r重合
|
|
v = min(v, dfs(l, k) + dfs(k, r) + w[l] * w[r] * w[k]);
|
|
return v;
|
|
}
|
|
|
|
int main() {
|
|
int n;
|
|
scanf("%d", &n);
|
|
for (int i = 1; i <= n; i++) w[i] = read();
|
|
|
|
// 初始化极值
|
|
for (int i = 1; i <= n; i++)
|
|
for (int j = 1; j <= n; j++)
|
|
f[i][j] = INF;
|
|
|
|
write(dfs(1, n));
|
|
return 0;
|
|
}
|