一开始看成了状压 dp，给我写得怀疑人生了。其实这就是个普通的 dp。
顺便一提
前序遍历指的是先输出根结点，然后分别遍历左子树和右子树。中序遍历指的是先遍历左子树，再输出根结点，最后遍历右子树。后序遍历同理。
设 $dp(i, j)$ 包含中序遍历为 i..j（按惯例，左闭右开）的二叉树能组成的最大 point 和对应的前序遍历。那么有：
$$
dp(i, j) = \max_{k = i}^{j - 1}(dp(i, k) * dp(k + 1, j) + \text{node_points}(k))
$$
注意这里对边界情况有特别要求，上面的式子没有考虑。那就是如果有一个子树为空的话，上式中的子树分数为另一个子树的分数；如果两个都是空的（这是个叶子结点），那么这个树的分数就是这个结点的分数。
有了上面的式子，就可以写出代码了。下面的代码中使用的是闭区间，从 1 开始数数，所以和上面的式子有一点细节上的出入。
这个算法的复杂度是 $O(n^3)$，但是 $n$ 很小所以没有问题。
#include "bits/stdc++.h"
using u32 = uint32_t;
using u64 = uint64_t;
struct DpRecord {
u64 point = 0;
std::vector<u32> preorder_traversal;
};
int main() {
u32 n;
std::cin >> n;
std::vector<u32> node_points(n + 1);
for (u32 i = 1; i <= n; ++i) {
std::cin >> node_points[i];
}
std::vector dp(n + 1, std::vector<DpRecord>(n + 1));
for (u32 i = 1; i <= n; ++i) {
// Special case for leaves.
dp[i][i].point = node_points[i];
dp[i][i].preorder_traversal.push_back(i);
}
for (u32 span_size = 2; span_size <= n; ++span_size) {
for (u32 i = 1, j = i - 1 + span_size; j <= n; ++i, ++j) {
u32 root;
u64 potential_max;
{ // Special case for borders.
auto const kIAsRoot = dp[i + 1][j].point + node_points[i];
auto const kJAsRoot = dp[i][j - 1].point + node_points[j];
if (kIAsRoot < kJAsRoot) {
root = j;
potential_max = kJAsRoot;
} else {
root = i;
potential_max = kIAsRoot;
}
}
for (u32 k = i + 1; k < j; ++k) {
auto const kPoint = dp[i][k - 1].point * dp[k + 1][j].point + node_points[k];
if (potential_max < kPoint) {
potential_max = kPoint;
root = k;
}
}
dp[i][j].point = potential_max;
auto& vec = dp[i][j].preorder_traversal;
vec.push_back(root);
for (auto const id : dp[i][root - 1].preorder_traversal) {
vec.push_back(id);
}
for (auto const id : dp[root + 1][j].preorder_traversal) {
vec.push_back(id);
}
}
}
std::cout << dp[1][n].point << '\n';
for (auto const id : dp[1][n].preorder_traversal) {
std::cout << id << ' ';
}
std::cout << '\n';
}
兄弟，你这个格式出现了鬼畜。下次可以在代码前后加上这个：
（上面的没有反斜线）