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.

56 lines
1.5 KiB

2 years ago
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
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 f[N][N];
LL w[N];
int n;
int main() {
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++)
// 两个点之间最小差距是2比如[1,3]这里面就有三角形需要求解如果小于2比如[1,2]
// 无法构成三角形就不需要求解无法构成的情况贡献值是0也是递推的起点否则全都是INF
// 就无法推起来了
j - i < 2 ? f[i][j] = 0 : f[i][j] = INF;
for (int len = 3; len <= n; len++) { // 区间范围最少是3个否则无法构建三角形
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
for (int k = l + 1; k < r; k++) // l<k<r才能构建三角形
f[l][r] = min(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
}
}
// 输出
write(f[1][n]);
return 0;
}