区间dp
定义dp[i][j]=从i合并到j最大能量
此时dp[i][j]可以表示一个珠子的能量
故有转移方程dp[i][j]=max{dp[i][k]+dp[k+1][k]+A[i]*A[k+1]*A[j+1]),i<=k<j;
为了规避环，将数组扩大两倍储存珠子能量
最后ans=max{dp[i][i+n-1]},1<=i<=n;
代码：
#include<bits/stdc++.h> using namespace std; const int N=210; int A[N],dp[N][N]; int main() { int n,ans=0; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&A[i]),A[i+n]=A[i]; for(int v=1;v<n;v++) for(int i=1;i<=2*n-v;i++) { int j=i+v; for(int k=i;k<j;k++) dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+A[i]*A[k+1]*A[j+1]); } for(int i=1;i<=n;i++) ans=max(ans,dp[i][i+n-1]); printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/greengenius/p/9241385.html