本题在洛谷上的链接：https://www.luogu.org/problemnew/show/P1063
额，和石子合并好像的QwQ。
的确和石子合并很像，我们定义状态dp[i][j]表示从第i颗到第j颗所能释放的最大能量，显然，dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+head[i]*tail[k]*tail[j])，可以认为是先将i到k合并成一颗珠子，再将k+1到j合并成一颗珠子，最后将两颗珠子合并（石子合并也可以这样想）。和石子合并一样，这里的珠子成了环，因此可以开两倍的数组，来处理。注意，这样在枚举左端点时i，是从1到2*n-i（2*n用不到）。
1 #include<cstdio> 2 inline int max(int a,int b) {return a>b?a:b;} 3 const int maxn=105; 4 int n,head[2*maxn],tail[2*maxn],dp[2*maxn][2*maxn],ans; 5 int main() { 6 scanf("%d",&n); 7 for(int i=1;i<=n;++i) {scanf("%d",&head[i]);head[n+i]=head[i];} 8 for(int i=1;i<=n;++i) tail[i]=i==n?head[1]:head[i+1],tail[n+i]=tail[i]; 9 for(int l=2;l<=n;++l) 10 for(int i=1;i<=2*n-l;++i) { 11 int j=i+l-1; 12 for(int k=i;k<j;++k) 13 dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+head[i]*tail[k]*tail[j]); 14 if(l==n) ans=max(ans,dp[i][j]); 15 } 16 printf("%d",ans); 17 return 0; 18 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9631835.html
