[NOIP2006] 能量项链

题意：

传送门

题解：

区间dp

断环为链，由于是环，要枚举从哪个数开始合并。

2,3,5,10可以看做是2,3,5,10,2这段区间的合并，然后直接最简单的区间dp即可

注意：i要逆序枚举

#include<cstdio>
#include<algorithm>
#define N 500
using namespace std;

int n,ans,a[N],dp[N][N];

int gi() {
  int x=0,o=1; char ch=getchar();
  while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
  if(ch=='-') o=-1;
  while(ch>='0' && ch<='9') x=10*x+ch-'0',ch=getchar();
  return x*o;
}

int main() {
	n=gi();
	for(int i=1; i<=n; i++) {
		a[i]=gi(),a[n+i]=a[i];
	}
	for(int j=1; j<=n<<1; j++) 	
		for(int i=j-2; i>=1; i--)
			for(int k=i+1; k<j; k++)
				dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]);
	for(int i=1; i<=n; i++) {
		ans=max(ans,dp[i][i+n]);
	}
	printf("%d", ans);
}