算法1
(DP) $O(n^3)$
时间复杂度
设最后一次合并时, 顺序在前的珠子 为起始时的第 k 个珠子(k从0开始)
则最后一次合并时,
前一个珠子的头标记为e[l], 尾标记为e[k+1]
后一个珠子的头标记为e[k+1], 尾标记为e[r+1]
则 f[l][r] = max(f[l][r], f[l][k] + f[k+1][r] + e[l]e[k+1]e[r+1])
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
const int C = 202;
int f[C][C];
int e[C];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i ++) {
cin >> e[i];
e[i + n] = e[i];
}
for (int len = 1; len <= n ; len ++)
for (int l = 0; l + len - 1 < 2 * n; l ++) {
int r = l + len -1;
for (int k = l; k < r; k ++ )
f[l][r] = max(f[l][k] + f[k+1][r] + e[l] * e[k+1] * e[r+1], f[l][r]);
}
int res = 0;
for (int i = 0; i < n; i ++) res = max(res, f[i][i+n-1]);
cout << res;
}