这题是区间dp的经典题目,和石子合并一样,但是我忘了石子合并了,毕竟我是当自己大一啥都没学,只是接触过,现在重学来的~..
说实话,因为解除了许多区间dp,但是以前对于有环的只知道×2,然后是用小区间更新大区间,但是一直没理解过它们,以至于简单的区间dp都没写出来,丢人...(主要是主观意识太强了,不理解,不会,就没深想)
合并一个区间会发生什么?似乎很简单吧...就是两个区间的中间那个元素没了,然后产生的价值...然后就可以很简单的转移了...
好菜啊!!!
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=205;
int a[N];
int f[N][N];//区间进行执行的最大值.
int main()
{
    int n,ans=-1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)   {scanf("%d",&a[i]);a[i+n]=a[i];}
    for(int i=2;i<=2*n;i++)//枚举区间右端点.
    {
        for(int j=i-1;j>=1&&i-j<n;j--)//枚举左端点
        {
            for(int k=j;k<=i-1;k++)//枚举是在哪合并的.将区间分成j~k,k+1~i.然后进行合并.
            {
                f[j][i]=max(f[j][i],f[j][k]+f[k+1][i]+a[j]*a[k+1]*a[i+1]);
                ans=max(ans,f[j][i]);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}