代码

#include <bits/stdc++.h>

using namespace std;

const int N = 55, M = 35;

typedef long long LL;

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

void mul(LL a[], LL b)
{
    LL t = 0;
    for (int i = 0; i < M; i ++ )
    {
        t += a[i] * b;
        a[i] = t % 10;
        t /= 10;
    }
}

void add(LL a[], LL b[])
{
    LL t = 0;
    for (int i = 0; i < M; i ++ )
    {
        t += a[i] + b[i];
        a[i] = t % 10;
        t /= 10;
    }
}

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()
{
    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[r]);
                mul(temp, w[k]);
                
                add(temp, f[l][k]);
                add(temp, f[k][r]);
                
                if (cmp(temp, f[l][r]) < 0)
                    memcpy(f[l][r], temp, sizeof temp);
            }
        }
    }
    
    print(f[1][n]);
    
    return 0;
}