题意：给出n个珠子，围成一圈，相邻位置相碰可以产生能量
每一个珠子都有两个能量值，可以定义为前跟后
一开始，前为其本身，后为其本身+1的位置的能量
相邻位置碰撞产生的能量为：前*后*前
碰撞后这两颗珠子融为一体，前为前者的前，后为后者的后
问：可以产生的最大能量为？
思路：很明显，不同的碰撞方式产生的能量不同；并且这是个圈圈；
所以我们要此数组后面再加一遍 （模拟圈）
然后就开始区间dp，长度从2到n进行枚举即可；
每一次枚举一个区间dp【i】【j】，这个区间形成的珠子，“前”为a[i]，“后”为a[j+1]（试着模拟一下就会知道是这样）
最后我们再枚举一下哪一个区间答案最大即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=2e2+10; 4 int dp[maxn][maxn]; 5 int a[maxn]; 6 int main() 7 { 8 int n; 9 scanf("%d",&n); 10 for(int i=1;i<=n;i++){ 11 scanf("%d",&a[i]); 12 a[i+n]=a[i]; 13 } 14 for(int len=1;len<n;len++){ 15 for(int i=1;i<=2*n;i++){ 16 int j=i+len; 17 if(j<=2*n){ 18 for(int k=i+1;k<=j;k++){ 19 dp[i][j]=max(dp[i][j],dp[i][k-1]+dp[k][j]+a[i]*a[k]*a[j+1]); 20 } 21 } 22 // printf("%d ",dp[i][j]); 23 } 24 // printf("\n"); 25 } 26 int ans=0; 27 for(int i=1;i<=n;i++) 28 ans=max(ans,dp[i][n+i-1]); 29 printf("%d\n",ans); 30 return 0; 31 }
原文：https://www.cnblogs.com/pangbi/p/12553253.html
