closefrom

区间dp能解决的问题就是通过小区间更新大区间，最后得出指定区间的最优解

个人认为，想要用区间dp解决问题，首先要确定一个大问题能够剖分成几个相同较小问题，且小问题很容易组合成大问题，从而从解决小问题逐渐解决大问题，体现的其实是分治的思想，只不过是通过dp用递推的方式解决了。比如floyd现在看来也属于区间dp 的一种。

本题应通过演算过程发现最终问题的解决可由两个相同规模较小的问题轻松地转化过来。（一般分治时只分成两个简化程序） 用f[l][r]表示以a[l]开头a[r]结尾的数串的最大和，如k为i,j之间任一节点，有f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]_a[k]_a[r]); 对l,r的定义自己一定要十分清晰，从而确定好循环的边界。

本题的小技巧：在环形问题中，可以选择(i+1)%n的方式，但也可以将n个元素复制一遍，变成2*n个元素，简化代码。

但也有问题随之而来，在更新时要将2*n个元素都更新，而不能只更新到前n个，否则访问到n+1~2n时会出错

//My AC Code:
#include <cstdio>
using namespace std;
int n,dp[205][205],ans=-1,nn[205];
int max(int a,int b){return a>b?a:b;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){scanf("%d",&nn[i]);nn[i+n]=nn[i];}
    
    for(int i=2;i<=n+1;i++){//这一层循环是用来控制 最后边的位置right
        for(int j=1;j+i-1<=2*n;j++){
            int r=j+i-1;//r的范围是2-2*n
            for(int k=j+1;k<=j+i-2;k++)// 如：若有三个数ABC，则 k表示为B这个数
                dp[j][r]=max(dp[j][r],dp[j][k]+dp[k][r]+nn[j]*nn[k]*nn[r]);
        }
        
    }
    for(int i=1;i<=n;i++){ans=max(ans,dp[i][n+i]);}//dp完之后从dp[i][n+i]中找，也就是找n个珠子
    printf("%d",ans);
    return 0;
}