代码耗时1100ms+

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;

const int MAXN = 55, MAXM = 35;

vector<int> f[MAXN][MAXN];
int w[MAXN];
int n;

vector<int> add(vector<int>& a, vector<int>& b)
{
    if (a.size() < b.size()) return add(b, a);
    vector<int> c;
    int t = 0;

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

    if (t) c.push_back(t);
    return c;
}

vector<int> mul(vector<int>& a, int b)
{
    vector<int> c;
    LL t = 0;

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

    return c;
}

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

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    vector<int> tmp;
    for (int len = 3; len <= n; ++len)
    {
        for (int l = 1; l + len - 1 <= n; ++l)
        {
            int r = l + len - 1;
            f[l][r] = vector<int>(MAXM, 1);
            for (int k = l + 1; k < r; ++k)
            {
                tmp.clear();
                tmp.push_back(w[l]);
                tmp = mul(tmp, w[k]), tmp = mul(tmp, w[r]);
                tmp = add(tmp, f[l][k]), tmp = add(tmp, f[k][r]);
                if (cmp(f[l][r], tmp)) 
                    f[l][r] = tmp;
            }
        }
    }

    for (int i = f[1][n].size() - 1; i >= 0; --i)
    {
        cout << f[1][n][i];
    }
    cout << endl;
}