蓝桥杯算法提高-能量项链-题解（Java代码）

解题思路:

注意事项:环形dp+区间dp

参考代码:

import java.util.Scanner;

public class llq1{

static int[]ball=new int[110*2];

static int[][]dp=new int[110*2][110*2];

public static void main(String[] args) {

Scanner s=new Scanner(System.in);

int n=s.nextInt();

for(int i=1;i<=n;i++) {

ball[i]=s.nextInt();

}

for(int i=n+1;i<=2*n;i++) {

ball[i]=ball[i-n];

}

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]=Math.max(dp[i][j], dp[i][k]+dp[k+1][j]+ball[i]*ball[k+1]*ball[j+1]);

}

}

}

int ans=0;

for(int i=1;i<=n;i++) {

ans=Math.max(ans, dp[i][i+n-1]);

}

System.out.println(ans);

}

}