$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题本身不难，分析思路跟之前的区间 DP 问题一样

我们考虑某一条边处在哪个三角形中，可以将整个多边形划分成 $n-2$ 个三角形

因此我们定义 $f[l][r]$ 表示集合为：对区间 $[l,r]$ 划分的所有可能，属性为最大值

由于区间长度最小值 3 ，并且不需要从更小的区间转移过来，因此区间长度初始值设为 3

状态转移方程为：

$$ f[l][r]=max(f[l][r],f[l][k]+f[k][r]+q[l]\times q[k] \times q[r]) $$

每个数的大小都是 $10^9$，有三个数相乘，并且会用 48 个这样的数相加，此时数字的位数已经到 30 了

因此 long long 是存不下的，我们需要额外写一个高精度

完整代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55, M = 35, INF = 0x3f3f3f3f;
typedef long long LL;
LL f[N][N][M];//每个f[l][r]均为一个十进制表示的长度为M的向量（不考虑符号位）
int q[N];
int n;

void add(LL a[], LL b[])
{
    static LL c[M];//这里必须定义成LL，因为后面的拷贝是用c的大小来进行的，如果是int的话c的大小会变小
    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)
{
    static LL c[M];
    memset(c, 0, sizeof c);
    LL t = 0;//这里的t需要在外面定义
    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()
{
    LL tmp[M];
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> q[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;
            for(int k = l + 1; k < r; k++)
            {
                memset(tmp, 0, sizeof tmp);
                tmp[0] = q[l];//tmp理应存储的是每一位数字，这里我们偷个懒，全部存在第一位，此时就需要保证t为long long，由于在高精度中会自动将t展开成 M 位，因此不影响
                mul(tmp, q[k]);
                mul(tmp, q[r]);
                add(tmp, f[l][k]);
                add(tmp, f[k][r]);
                if(cmp(f[l][r], tmp) > 0) memcpy(f[l][r], tmp, sizeof tmp);
            }
        }
    print(f[1][n]);
   return 0; 
}