luogu_P1063 能量项链

传送门：https://www.luogu.org/problem/P1063

简单环形区间dp，把区间增大一倍，按照题意转移即可。

#include<cstdio>
#include<algorithm>
#define R register
using namespace std;
int n,h[220],t[220];
long long f[220][220],ans;
int main (){
    scanf("%d",&n);
    for(R int i=1;i<=n;i++) scanf("%d",&h[i]),h[i+n]=h[i];
    for(R int i=1;i<=2*n;i++){
        t[i]=h[i+1];
        if(i==2*n) t[i]=h[1];
    }
    for(R int len=1;len<=n;len++){
        for(R int l=1;l<=2*n-len+1;l++){
            int r=l+len-1;
            for(R int k=l;k<r;k++){
                f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+h[l]*t[k]*t[r]);
            }
        }
    }
    for(R int i=1;i<=n+1;i++){
        ans=max(ans,f[i][i+n-1]);
    }
    printf("%lld
",ans);
    return 0;
}