算法:区间 DP
时间复杂度:$O(n^3)$
该题在套路上和算法基础课的 AcWing 282. 石子合并 是类似的,我们具体来分析一下该题。
设 $f[l][r]$ 表示在区间 $[l, r]$ 中满足中序遍历的加分二叉树的最大值。
首先将二叉树问题转变为区间 $dp$ 问题,给定一棵树用 $1, 2, 3 …, n$ 的中序序列表示,其核心在于枚举根节点,比如确定根节点为 $k$ 时其加分二叉树可得最高分。
则:$f[l][r] = f[l][k - 1] \times f[k + 1][r] + w[k]$
进一步分析发现又是一个子问题,则按照区间 $dp$, 长度从小到大去做即将问题分解为子问题,逐个击破。
至于求解该序列的前序遍历,则可以再开一个数组如 $g[l][r]$ 用来记录区间 $[l, r]$ 的根节点,再按前序遍历递归输出即可。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
int n;
int w[N], f[N][N], g[N][N];
void print(int l, int r)
{
if (l > r) return ;
else {
int root = g[l][r];
cout << root << ' ';
print(l, root - 1);
print(root + 1, r);
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) cin >> w[i];
for (int len = 1; len <= n; ++len) { // 区间 dp
for (int l = 1; l + len - 1 <= n; ++l) {
int r = l + len - 1;
if (l == r) {
f[l][r] = w[r]; // 根节点(取 w[k])
g[l][r] = r;
}
else {
for (int k = l; k <= r; ++k) {
int left = l == k ? 1 : f[l][k - 1];
int right = r == k ? 1 : f[k + 1][r];
int score = left * right + w[k];
if (f[l][r] < score) {
f[l][r] = score;
g[l][r] = k;
}
}
}
}
}
cout << f[1][n] << endl;
print(1, n);
return 0;
}