P1063 能量项链 区间DP

P1063 能量项链

年轻人不要老刷水题qwq

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int f[300][300];
int a[300];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        a[i+n]=a[i];
    }
    int ans=-1;
    for(int v=3;v<=n+1;v++)
        for(int l=1;l<=2*n-v+1;l++)
        {
            int r=l+v-1;
            for(int i=l+1;i<r;i++)
            {
                f[l][r]=max(f[l][r],f[l][i]+f[i][r]+a[l]*a[i]*a[r]); 
                ans=max(ans,f[l][r]);
            }
//            printf("%d %d %d?
",l,r,f[l][r]);
        }
    printf("%d",ans);
    
}