还可以的dp。

区间动规 重点就是将整体划分为区间，小区间之间合并获得大区间 状态转移方程的推导如下 一、将珠子划分为两个珠子一个区间时，这个区间的能量 === 左边珠子右边珠子右边珠子的下一个珠子 二、区间包含 333 个珠子，可以是左边单个珠子的区间 +++ 右边两珠子的区间，或者左边两珠子的区间右边 +++ 单个珠子的区间 即，先合并两个珠子的区间，释放能量，加上单个珠子区间的能量（单个珠子没有能量。。） Energy=maxEnergy=maxEnergy=max (两个珠子的区间的能量 +++ 单个珠子区间的能量，单个珠子的区间的能量 +++ 两个珠子的区间的能量 ） 三、继续推 444 个珠子的区间， 555 个珠子的区间。 于是可以得到方程： Energy=maxEnergy=maxEnergy=max （不操作的能量，左区间合并后的能量 +++ 右区间合并后的能量 +++ 两区间合并产生能量） 两区间合并后产生的能量 === 左区间第一个珠子右区间第一个珠子总区间后面的一个珠子

#include<bits/stdc++.h> using namespace std; const int N=105; int a[2N],ans,n,dp[2N][2N],b[2N]; int main(){ scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",&a[i]); a[i+n] = a[i]; } //a[n2+1] = a[1]; for(int i=1;i<=2n;++i){ b[i] = a[i+1]; } for(int len=2;len<=n;++len){ for(int l=1;l+len-1<=2*n;++l){ int r=l+len-1; for(int i=l;i<r;++i){ dp[l][r] = max(dp[l][r],dp[l][i]+dp[i+1][r]+a[l]*b[i]*b[r]); }

前言 区间dp能解决的问题就是通过小区间更新大区间，最后得出指定区间的最优解 个人认为，想要用区间dp解决问题，首先要确定一个大问题能够剖分成几个相同较小问题，且小问题很容易组合成大问题，从而从解决小问题逐渐解决大问题，体现的其实是分治的思想，只不过是通过 dp 用递推的方式解决了。比如 floyd 现在看来也属于区间dp的一种。 代码思路 本题应通过演算过程发现最终问题的解决可由两个相同规模较小的问题轻松地转化过来。（一般分治时只分成两个简化程序） 用 fl,rf_{l, r}fl,r 表示以 ala_lal 开头 ara_rar 结尾的数串的最大和，如 kkk 为 i,ji,ji,j 之间任一节点，有 f[l][r]=max(fl,r,fl,k+fk,r+alak∗ar)f[l][r]=max(f_{l, r},f_{l, k}+f_{k, r}+a_la_k*a_r)f[l][r]=max(fl,r ,fl,k +fk,r +al ak ∗ar ) 对l,r的定义自己一定要十分清晰，从而确定好循环的边界。 本题的小技巧：在环形问题中，可以选择 (i+1)(i+1)%n(i+1) 的方式，但也可以将 nnn 个元素复制一遍，变成 2n2n2n 个元素，简化代码。 但也有问题随之而来，在更新时要将 2n2n2n 个元素都更新，而不能只更新到前 nnn 个，否则访问到 n+1n+1n+1 ~ 2n2n2n 时会出错。 代码