动态规划

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//递归
//int Func(vector<int>& arr, int L, int R) {
//    //此时只有一个气球，直接打爆
//    if (L == R) {
//        return arr[L - 1] * arr[L] * arr[R + 1];
//    }
//    //如过arr[L]或者arr[R] 是最后打爆的
//    int Max = max(arr[L - 1] * arr[L] * arr[R + 1] + Func(arr, L + 1, R),
//        arr[L - 1] * arr[R] * arr[R + 1] + Func(arr, L, R - 1));
//    //尝试每一中间位置最后被打爆
//    for (int i = L + 1; i < R; ++i) {
//        Max = max(Max, arr[L - 1] * arr[i] * arr[R + 1] + Func(arr, L, i - 1) +
//            Func(arr, i + 1, R));
//    }
//    return Max;
//}

int main() {

    int n;
    while (cin >> n) {
        vector<int> arr(n);
        for (int i = 0; i < n; ++i) {
            cin >> arr[i];
        }
        vector<int> v(n + 2);
        v[0] = 1;
        v[n + 1] = 1;
        for (int i = 0; i < n; ++i) {
            v[i + 1] = arr[i];
        }
        //动态规划
        //根据递归的终止条件确定初始值
        vector<vector<int>> dp(n + 2,vector<int>(n + 2));
        for (int i = 1; i <= n; ++i) {
            dp[i][i] = v[i - 1] * v[i] * v[i + 1];
        }
        //根据递归式可以看出，当前的dp值只与左边和下边有关，所以自底向上更新
        for (int L = n; L >= 1; --L) {
            for (int R = L + 1; R <= n; ++R) {

                //最后打爆v[L]的分数
                int final_L = v[L - 1] * v[L] * v[R + 1] + dp[L + 1][R];
                //最后打爆v[R]的分数
                int final_R = v[L - 1] * v[R] * v[R + 1] + dp[L][R - 1];
                dp[L][R] = max(final_L,final_R);
                //尝试最后打中间
                for (int k = L + 1; k < R; ++k) {
                    dp[L][R] = max(dp[L][R],v[L - 1] * v[k] * v[R + 1] + dp[L][k - 1] + dp[k + 1][R]);
                }
            }
        }
        cout << dp[1][n] << endl;
    }
    return 0;
}