dp[i][j]代表i到j这一段的项链所含的最大聚能量
dp[i][j]=max(dp[i][k]+dp[k+1][j]+num[i]*num[k+1]*num[j+1]);(i<=k<j);
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int num[501];
int dp[501][501];
int dos(int x,int y)
{
if(dp[x][y])
{
return dp[x][y];
}
if(y-x==1)
{
dp[x][y]=num[x]*num[y]*num[y+1];
return dp[x][y];
}
if(y-x==0)
{
dp[x][y]=0;
return 0;
}
int ans=0;
for(int i=x;i+1<=y;i++)
{
ans=max(ans,dos(x,i)+dos(i+1,y)+num[x]*num[i+1]*num[y+1]);
}
dp[x][y]=ans;
return ans;
}
int main()
{
int n,i;
cin>>n;
for(i=0;i<n;i++)
{
cin>>num[i];
num[i+n]=num[i];
}
int maxn=0;
for(i=0;i<n;i++)
{
maxn=max(maxn,dos(i,i+n-1));
}
cout<<maxn<<endl;
return 0;
}