python/TangDou/AcWing/Section/1069_GJD.cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 210;
const int M = 35;
const int INF = 0x3f3f3f3f;
int n;
LL f[N][N][M];
LL w[N];

// 判断a>b
bool cmp(LL a[], LL b[]) {
    for (int i = M - 1; i >= 0; i--) { // 直接从高位进行比较,如果某一位a[i]>b[i]，则说明a比b这个数大
        if (a[i] > b[i]) return true;
        if (a[i] < b[i]) return false;
    }
    return false;
}

// 直接从0位(个位)加，一直加到最高位M-1位
void add(LL a[], LL b[]) {
    LL c[M] = {0}, t = 0;
    for (int i = 0; i < M; i++) {
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof c);
}

// 从0位(个位)开始乘，一直乘到最高位M-1位
void mul(LL a[], LL b) {
    LL c[M] = {0}, t = 0;
    for (int i = 0; i < M; i++) {
        t += a[i] * b;
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof c);
}

// 打印高精度结果数组
void print(LL a[]) {
    int k = M - 1;
    while (k && !a[k]) k--; // 输出之前要将所有的前导0都去掉
    for (int i = k; i >= 0; i--) printf("%lld", a[i]);
    puts("");
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);

    for (int len = 3; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;

            f[l][r][M - 1] = 1; // 因为高精度数组是高位在右，低位在左，这里设置的是最高位为1，目的是什么呢？

            for (int k = l + 1; k < r; k++) { // 枚举中间点
                LL t[M] = {0};                // 临时高精度数组
                t[0] = 1;                     // 乘法的世界本原
                mul(t, w[l]);                 // 高精度乘法
                mul(t, w[k]);                 // 高精度乘法
                mul(t, w[r]);                 // 高精度乘法
                add(t, f[l][k]);              // 高精度加法
                add(t, f[k][r]);              // 高精度加法
                // 得到新的最大值，更新
                if (cmp(f[l][r], t)) memcpy(f[l][r], t, sizeof t);
            }
        }
    }
    // 输出
    print(f[1][n]);
    return 0;
}