题目描述

给定一个具有 N 个顶点的凸多边形，将顶点从 1 至 N 标号，每个顶点的权值都是一个正整数。将这个凸多边形划分成 N-2 个互不相交的三角形，试求这些三角形顶点的权值乘积和至少为多少。

输入格式

输入第一行为顶点数 N

第二行依次为顶点 1 至顶点 N 的权值。

输出格式

输出仅一行，为这些三角形顶点的权值乘积和的最小值。

样例

样例输入

复制5
121 122 123 245 231

样例输出

复制12214884

_____________________________________________________________________________

写作不易，点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

_____________________________________________________________________________

#include <bits/stdc++.h>
using namespace std;
__int128_t f[55][55], n, a[55];
inline __int128_t read() {//快读快写，数据量太大了
    __int128_t x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
inline void print(__int128_t x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}
int main() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n - 2; i++) f[i][i + 2] = a[i] * a[i + 1] * a[i + 2];
    for (int len = 4; len <= n; len++) {
        for (int l = 1; l <= n - len + 1; l++) {
            int r = l + len - 1;
            f[l][r] = 1e30;
            for (int i = l; i <= r; i++) {
                f[l][r] = min(f[l][r], f[l][i] + f[i][r] + a[l] * a[r] * a[i]);
            }
        }
    }
    print(f[1][n]);
}