谢谢

1、阶段和状态：

很明显的动规，类似“石子合并”或“矩阵相乘”，此题主要不同在于环的处理问题.

环的处理方法：将长为n的环展开为长为2n的链来处理。

a[i]：表示第i颗珠子的头标记；a[n+i]=a[i];

b[i]：表示第i颗珠子的尾标记；b[i]=a[i+1];b[2*n]=a[1];

f[i][j]：表示从第i颗到第j颗珠子合并为一颗珠子释放的最大能量;

2、状态转移方程：

初始化： f[i][i+1]=a[i]*b[i]*b[i+1];

转移方程：f[ij]=min{f[i][k]+f[k+1][j]+a[i]*b[i]*b[i+1]}(i<=k<=j-1)

Answer=max{f[i][i+n-1]},(1<=i<=n)

时间复杂度为O(n^3)。

这道题被数据坑了 N开100不行。。我一开始看到最后两个错了很惊讶 开1000就AC了= =