分析

P.S

高精度的vector模板还是不熟，处处是坑

vector高精度 + 区间划分dp

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 51, INF = 1e9, M = 35; 
typedef long long LL;  
vector<int>f[N][N];
LL w[N];

void print(vector<int> & a)
{
    for(int i = a.size() - 1; i >= 0; i--)
        cout << a[i];
    cout << endl;
}

vector<int> add(vector<int>  a, vector<int>  b)
{
    vector<int> c;
    if(a.size() < b.size())return add(b, a);
    int t = 0;
    for(int i = 0; i < a.size(); ++i)
    {
        t += a[i];
        if(i < b.size())t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    if(t) c.push_back(t);
    return c;
}


void mul(vector<int> & a, LL b)
{
    vector<int> c;LL t = 0;
    for(int i = 0; i < a.size() || t > 0; ++i)
    {
        if(i < a.size())t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    a = c;
}

bool cmp(vector<int> &a, vector<int> &b)
{
    int n = a.size(), m = b.size();
    if(n != m)return n > m;
    else
    {
        for(int i = n - 1; i >= 0; i--)
            if(a[i] == b[i])continue;
            else return a[i] > b[i];
    }
}


int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> w[i];
    }
    for(int len = 2; len < n; ++len)
        for(int l = 1; l + len <= n; ++l)
        {
            int r = l + len;
            for(int i = 0; i < M; ++i)
                f[l][r].push_back(1);
            for(int k = l + 1; k < r; ++k)
            {
                vector<int> temp;
                temp.push_back(w[l]);
                mul(temp, w[k]);
                mul(temp, w[r]);
               // print(temp);
                //print(f[l][k]);
                temp = add(temp, f[l][k]);
                //print(temp);
                //cout << k << endl;

                temp = add(temp, f[k][r]);
                if(cmp(f[l][r], temp))
                    f[l][r] = 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;
}