能量项链

zztlen · 2018-04-26 17:02:36 · 个人记录

#include<bits/stdc++.h>
using namespace std;
int n,a[1001],f[1001][1001],maxx;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1,j=n+1;i<=n,j<=2*n;i++,j++)
        a[j]=a[i];
    for(int j=1;j<2*n;j++)
    for(int i=j;i>=1&&i>j-n;i--)
    for(int k=i;k<j;k++)
        f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[j+1]*a[k+1]);
    for(int i=1;i<=n;i++)
    maxx=max(maxx,f[i][i+n-1]);
    cout<<maxx;
}