概览

查看数据范围，1e9, 最多501e91e9*1e9 所以需要写高精度

long long 1e27

int64 1e18
int128 1e36

多边形划分有多种形式，枚举的时候一定利用的是之前已经连成功的边

回想合并石子
f[1,3]: 合并1到3的所有方式的代价

f[i,j]: 合并所有从i到j的所有方式的Min

状态划分
f[1, n] = min(f[1, n], f[1, k] + f[k, n] + w[1]w[k]w[n])

往往从最后一步进行思考
最后一步划分，左右和最终合并三个部分是完全独立的，所以可以用这个做。
从题解来倒推状态方程式

当剩下一个三角形时停止，f[1, n]

题解

f[l, r]: 所有将(l,l+1),(l+1,l+2),..(r-1,r),(r,l)这个多边形划分为三角形的方案

注意理解本质从哪个顶点开始都是一样的，所以枚举任意一种即可，即链式的

高精度的偷懒做法

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55, M = 35;

typedef long long LL;
int n;
int w[N];
LL f[N][N][M];

void add(LL a[], LL b[]) {
    LL c[M];
    memset(c, 0, sizeof c);
    for (int i = 0, t = 0; i < M; i ++) {
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof c);
}

void mul(LL a[], LL b) {
    LL c[M];
    memset(c, 0, sizeof c);
    LL t = 0;
    for (int i = 0; i < M; i ++) {
        t += a[i] * b;
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof c);
}

int cmp(LL a[], LL b[]) {
    for (int i = M - 1; i >= 0; i --)
        if (a[i] > b[i]) return 1;
        else if (a[i] < b[i]) return -1;
    return 0;
}

void print(LL a[]) {
    int k = M - 1;
    while(k && !a[k]) k --;
    while(k >= 0) cout << a[k --];
    cout << endl;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> w[i];

    LL temp[M];
    for (int len = 3; len <= n; len ++) {
        for (int i = 1; i + len - 1 <= n; i ++) {
            int l = i, r = i + len - 1;
            f[l][r][M - 1] = 1;

            for (int k = l + 1; k < r; k ++) {
                memset(temp, 0, sizeof temp);
                temp[0] = w[l];
                mul(temp, w[k]), mul(temp, w[r]);
                add(temp, f[l][k]), add(temp, f[k][r]);
                if (cmp(f[l][r], temp) > 0)
                    memcpy(f[l][r], temp, sizeof temp);
            }
        }
    }
    print(f[1][n]);
    return 0;
}