题目来自洛谷试炼场-普及组-更要技巧的动规与记忆化
题目链接/problem/P1063
题目的大致意思就是让N个珠子合在一起，要求释放的能量最大。规则是：例如：设N=4，44颗珠子的头标记与尾标记依次为(2,3) (3,5) (5,10) (10,2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j,k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：
(4⊕1)=60=10×2×3=60。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为：
((4⊕1)⊕2)⊕3）=10×2×3+10×3×5+10×5×10=710。
输入格式
第一行是一个正整数N(4≤N≤100)，表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过10001000。第ii个数为第ii颗珠子的头标记(1≤i≤N)，当i<N时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。
至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。
输出格式
一个正整数E(E≤2.1×(1e9))，为一个最优聚合顺序所释放的总能量。
输入输出样例输入 #1 复制42 3 5 10输出 #1 复制710
算法
刚拿到这个题目时，第一反应是直接暴力模拟运算出所有的结果，找到最大能量，可小同志的想法还是太简单，两组数据WA。随后看到有人说是区间dp——哦吼可以试试哦。
这里的dp其实用到的有一种分治思想的感觉我们划定一个区间，区间内逐次用一个分割变量将区间分开，再将两个区间内的状态相加一起，再加上左边和右边珠子合并时释放的能量，取最大值。
简单一点观察状态转移方程就是dp[l][r]=max(dp[l][r], dp[l][k]+dp[k][r]+a[l]*a[k]*a[r]);
在上式中：l和r是区间的左右端，k是区间中间的一个分割点。最后一个三连乘是左右合并释放的能量——这样看就一目了然
源码
#include<iostream>#include<algorithm>using namespace std;int dp[405][405];int n,a[205]; int main() {cin>>n;//环状展开 for(int i=1; i<=n; i++) {cin>>a[i];a[n+i]=a[i];} //区间长度 for(int i=2; i<=n+1; i++) {for(int l=1; l+i-1<=2*n; l++) {int r=l+i-1;//区间内选区 for(int k=l+1; k<=r-1; k++){//分治与dp dp[l][r]=max(dp[l][r], dp[l][k]+dp[k][r]+a[l]*a[k]*a[r]);}}}int ans=0;for (int i=1;i<=n;i++) ans=max(ans,dp[i][n+i]);cout << ans;return 0;}
