$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题的处理思路跟 AcWing 1068. 环形石子合并 很相似，不同的是区间的定义上

$f[l,\ r]$ 表示集合为：对区间 $[l,\ r)$ 内的石子进行合并的所有方案，属性为能量的最大值

假设现在有三个石头：$2,\ 3,\ 5$，即此时区间长度为 3

为了计算的便利，这三个石头我们表示为：$(2,3)$、$(3,5)$、$(5,2)$

当我们合并一二块石头时，有：$2\times 3\times5$

也就是合并 2 和 3 时，我们需要带上 5；进一步，如果我们需要计算 2，3，5，我们就需要带上 2，组成 2 3 5 2这个序列

也就是所求的区间长度由 3 增加到 4

这就是为什么我们需要将 $f[l,r]$ 的定义区间为 $[l,r)$ ，因为当 $l=r$ 时，区间不存在；$r=l+1$ 时，区间依旧不存在，此时表示区间内只有一个石子（左端点 $l$）

因此，我们用这种区间定义刚好可以用 4 个数来表示 3 个石子

此时不难写出状态转移方程：

$$ f[l][r]=max(f[l][r],f[l][k]+f[k][r]+q[l]\times q[k] \times q[r]) $$

我们最后会将整个区间合并为 3 个石子，石子编号为 $l,\ k,\ r$ ，而当 $l=k$ 或 $l=k-1$ 时，都会至多保留 1 个石子

往后的处理就跟环形石子合并一样了，不过我们最后所求的区间长度变为 $n+1$

完整代码：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 210;

int q[N], f[N][N];
int n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> q[i];
        q[i + n] = q[i];
    }
    for(int len = 3; len <= n + 1; len++)
    {
        for(int l = 1; l + len - 1 <= 2 * n; l++)
        {
            int r = l + len - 1;
            for(int k = l + 1; k < r; k++)
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + q[l] * q[k] * q[r]);
        }
    }
    int ans = -0x3f3f3f3f;
    for(int i = 1; i <= n; i++)
        ans = max(ans, f[i][i + n]);
    cout << ans << endl;
    return 0;
}