这道题的处理思路跟 AcWing 1068. 环形石子合并 很相似,不同的是区间的定义上
f[l, r] 表示集合为:对区间 [l, r) 内的石子进行合并的所有方案,属性为能量的最大值
假设现在有三个石头:2, 3, 5,即此时区间长度为 3
为了计算的便利,这三个石头我们表示为:(2,3)、(3,5)、(5,2)
当我们合并一二块石头时,有:2×3×5
也就是合并 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]×q[k]×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;
}