$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

• $1. 状态表示$
  $集合：区间[l,r]内的顶点划分三角形后各权值乘积之和$
  $属性：\min$

• $2. 状态转移$
  $f[l][r]=\min\{f[l][k]+f[k][r]+w[l]\cdot w[k]\cdot w[r] \}\ (l< k < r)$

• $3. 为什么不用断环成链？$
  $因为划分三角形后，凸多边形的所有边都一定是某个三角形的一边，即每条边都一定存在$

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 55, M = 30;

int n;
int w[N];
LL f[N][N][M];
LL temp[M];

//高精度乘法
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 add(LL a[],LL b[])
{
    LL c[M]={0};
    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);
}

//高精度比较
int cmp(LL a[],LL b[])
{
    for(int i=M-1;i>=0;i--)
    {
        if(a[i]>b[i]) return 1;
        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--];
}

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++) cin>>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; //正无穷
            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(temp,f[l][r])<0) memcpy(f[l][r],temp,sizeof temp);

                //上述代码等价于f[l][r]=min(f[l][r],f[l][k]+f[k][r]+w[l]*w[k]*w[r]);
            }
        }

    print(f[1][n]);

    return 0;
}