我也想要能量项链

解题思路:                             区间DP解法

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
int n,a[1100];
int dp[1100][1100];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];//模拟环
    }
    for(int len=2;len<=n;len++){//枚举长度
        for(int i=1;i+len-1<=2*n;i++){//枚举起始位置
            int j=i+len-1;//枚举结束位置
            for(int k=i;k<j;k++){//枚举中间位置
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1]);
            }
        }
    }
    int kkk=-1;
    for(int i=1;i<=2*n;i++){
        for(int j=1;j<=2*n;j++){
            kkk=max(kkk,dp[i][j]);//找到最大的dp值
        }
    }
    cout<<kkk<<endl;
    return 0;
}