给定一个具有 N 个顶点的凸多边形，将顶点从 1 至 N 标号，每个顶点的权值都是一个正整数。

将这个凸多边形划分成 N−2 个互不相交的三角形，对于每个三角形，其三个顶点的权值相乘都可得到一个权值乘积，试求所有三角形的顶点权值乘积之和至少为多少。

输入格式

第一行包含整数 N，表示顶点数量。

第二行包含 N 个整数，依次为顶点 1 至顶点 N 的权值。

输出格式

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

数据范围

N≤50,

数据保证所有顶点的权值都小于109

输入样例：

5

121 122 123 245 231

输出样例：

12214884

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

using namespace std;
typedef long long LL;

const int N = 55;
int w[N];
vector<int> f[N][N];
int n;

bool cmp(vector<int> &a, vector<int> &b)
{
    if (a.size() != b.size()) return a.size() > b.size();
    for (int i = 0; i < a.size(); i ++ ) //此处debug 找了很久没有太注意a是正序的 不需要逆转！！！！！
        if (a[i] != b[i])
            return a[i] > b[i];
    return true;
}
vector<int> add(vector<int> a, vector<int> b)
{
    vector<int> c;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int t = 0;
    for (int i = 0; i < a.size() || i < b.size(); i ++ )
    {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    while (t) c.push_back(t % 10), t /= 10;
    reverse(c.begin(), c.end());
    return c;
}
vector<int> mul(vector<int> a, LL b)
{
    vector<int> c;
    LL t = 0;
    reverse(a.begin(), a.end());
    for (int i = 0; i < a.size(); i ++ )
    {
        t += b * a[i];
        c.push_back(t % 10);
        t /= 10;
    }
    while (t) c.push_back(t % 10), t /= 10;
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    reverse(c.begin(), c.end());
    return c;
}
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;
            for(int k = l + 1; k < r; k ++){
                auto c1 = mul(mul({w[l]}, w[k]), w[r]);
                auto c2 = add(f[l][k], f[k][r]);
                auto c3 = add(c1, c2);
                if(f[l][r].empty() || cmp(f[l][r], c3)) f[l][r] = c3;
            }
        }
    auto res = f[1][n];
    for(int i = 0; i < res.size(); i ++) cout << res[i];

    return 0;
}