设f[l][r]表示合并[l,r]得到的最大价值
边界:$f[i][i]=0$
转移:枚举断点$k(l\le k<r)$,用$f[l][k]+f[k+1][r]+a[l]\times a[k+1]\times a[r+1]$更新就好了.
时间复杂度显然$O(n^3)$,注意断环为链即可.
/**********/省略快读
#define MAXN 511
ll f[MAXN][MAXN],a[MAXN];
int main()
{
ll n=read();
for(ll i=1;i<=n;++i)a[i+n]=a[i]=read();
a[n+n+1]=a[1];
for(ll i=1;i<=(n<<1);++i)f[i][i]=0;
for(ll len=2;len<=n;++len)
for(ll l=1;l+len-1<=(n<<1);++l)
{
ll r=l+len-1;
for(ll k=l;k<r;++k)
umax(f[l][r],f[l][k]+f[k+1][r]+a[l]*a[k+1]*a[r+1]);
}
ll ans=0;
for(ll i=1;i<=n;++i)
umax(ans,f[i][i+n-1]);
printf("%lld",ans);
return 0;
}
断点是什么意思呀
就是把$[l,r]$断成$[l,k]$和$[k+1,r]$