题目描述

blablabla

样例

blablabla

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
//因为要高精度，所以要考虑如何存储、如何运算
//如何存储？ 存储，使用一个二维的vector存储状态转移方程，一个一维vector逆序存储每个点的值； 
//如何运算？ 因为运算要存储中间结果，可以用一个vector存储中间结果；
//因为本来就是逆序存储，所以在运算的时候就不要在逆序了，只需在输出时逆序一下答案
const int N = 55;
vector<int> f[N][N], val[N];
int n;

//高精度乘法
void mul(const vector<int>& A,const vector<int>& B,vector<int>& C) {
    C.assign(A.size() + B.size(), 0);

    for (int i = 0; i < (int)A.size(); i++)
        for (int j = 0; j < (int)B.size(); j++)
            C[i + j] += A[i] * B[j];

    int t = 0;
    for (int i = 0; i < C.size(); i++) { 
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return ;
}

//高精度加法
void add(const vector<int>& A, const vector<int>& B, vector<int>& C) {
    int w = 0, st = 0,i = 0, j = 0;
    while (i < A.size() || j < B.size()) {
        w += st, st = 0;
        if (i < A.size()) w = w + A[i],i++;
        if (j < B.size()) w = w + B[j],j++;
        if (w >= 10) w = w % 10, st = 1;
        C.push_back(w);
        w = 0;
    }
    if (st) C.push_back(1);
}


//比较
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];
}

//输出
void print(vector<int>& A) {
    reverse(A.begin(), A.end());
    for (int i = 0; i < A.size(); i++)
        cout << A[i];
}
int main() {
    int v;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v;
        while (v){
            val[i].push_back(v % 10);
            v /= 10;
        }
    }
    for (int j = 2; j < n; j++) {
        for (int i = 1; i <= n - j; i++) {
            int l = i, r = i + j;
            for (int k = l + 1; k < r; k++) {
                vector<int> temp[4];
                mul(val[l], val[k], temp[0]);
                mul(temp[0], val[r], temp[1]);
                add(f[l][k], f[k][r], temp[2]);
                add(temp[2], temp[1], temp[3]);
                if (f[l][r].size() == 0 || cmp(f[l][r], temp[3])) f[l][r] = temp[3];
            }
        }
    }
    print(f[1][n]);
    return 0;
}