题解 | 能量项链

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

int main() {
    int n ;
    cin >> n;
    vector<int> input(n);
    for (int i = 0 ; i < n ; i++) {
        cin >> input[i];
    }

    vector<pair<int, int>> boxs;

    for (int i = 0 ; i < n ; i++) {
        if ( i == n - 1 ) {
            boxs.push_back({input[n - 1], input[0]});
        } else {
            boxs.push_back({input[i], input[i + 1]});
        }
    }

    for (int i = 0 ; i < n ; i++) {
        boxs.push_back(boxs[i]);
    }


    int maxSum = 0;

    for (int start = 0 ; start <= n - 1 ; start++) {

        vector<pair<int, int>> temp_boxs;
        for (int i = start ; i < start + n ; i++) {
            temp_boxs.push_back(boxs[i]);
        }

        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        for (int len = 2 ; len <= n ; len++) {
            for (int i = 0 ; i + len - 1 <= n - 1 ; i++) {
                int j = i + len - 1;
                dp[i][j] = max(dp[i][j - 1] + temp_boxs[i].first * temp_boxs[j].first * temp_boxs[j].second,
                               dp[i + 1][j] + temp_boxs[i].first * temp_boxs[i].second * temp_boxs[j].second);
                 int tempMax = 0;
                 for(int k = i ; k < j ; k++){
                    tempMax = max(tempMax,dp[i][k]+ dp[k+1][j] + temp_boxs[i].first * temp_boxs[k].second * temp_boxs[j].second);
                 }

                 dp[i][j] = max(dp[i][j],tempMax);

            }
        }

        maxSum = max(maxSum , dp[0][n-1]);


    }

    cout<<maxSum<<endl;







}