题目描述
设一个 \(n\) 个节点的二叉树 tree 的中序遍历为（\(1,2,3,…,n\)），其中数字 \(1,2,3,…,n\) 为节点编号。
每个节点都有一个分数（均为正整数），记第 \(i\) 个节点的分数为 \(d_i\)，tree 及它的每个子树都有一个加分，任一棵子树 subtree（也包含 tree 本身）的加分计算方法如下：
subtree的左子树的加分 \(×\) subtree的右子树的加分 \(＋\) subtree的根的分数
若某个子树为空，规定其加分为 \(1\)。
叶子的加分就是叶节点本身的分数，不考虑它的空子树。
试求一棵符合中序遍历为（\(1,2,3,…,n\)）且加分最高的二叉树 tree。
要求输出：
（1）tree的最高加分
（2）tree的前序遍历
输入格式
第 \(1\) 行：一个整数 \(n\)，为节点个数。
第 \(2\) 行：\(n\) 个用空格隔开的整数，为每个节点的分数（\(0<\)分数\(<100\)）。
输出格式
第 \(1\) 行：一个整数，为最高加分（结果不会超过int范围）。
第 \(2\) 行：\(n\) 个用空格隔开的整数，为该树的前序遍历。如果存在多种方案，则输出字典序最小的方案。
解题思路
\(\qquad\)这题初看没有入手点，但是题目有一个特殊的条件：中序遍历是\(1\sim n\)的升序，这也就代表我们可以抽象一下，将这棵树压扁，就可以到一个数轴上，是一个完整的区间\([1,n]\)，所以我们可以考虑一下区间\(DP\)。
状态表示
\[用f(l,r)表示数轴上区间[l,r]的最大加分 \]状态计算
\(\qquad\)一个区间的切割方法就是：对于区间\(f[l,r]\)，我们在这个子树上假设它的根节点是\(k\)，那么在\(k\)左边的区间都是以\(k\)为根的二叉树的左子，右边区间同理。所以对于以\(k\)为根的树，左子为\([l,k-1]\)，右子为\([k+1,r]\)，根据题目的加分规则，那$$\large score_{tree} = score_{left}\times score_{right} + w_{root}$$
\(\qquad\)此外还要注意，因为二叉树允许没有左子或者没有右子，因此\(k\)应该在\([l,r]\)而非\([l+1,r-1]\)枚举，并且对于\(l=k\)的情况，\(score_{left}=1\)，右子同理。
状态统计
\(\qquad\)由于题目需要输出二叉树的前序遍历，所以我们在\(DP\)的时候要保存一些信息。
补充：二叉树的前序遍历，先输出根，再递归左子，再递归右子。
\(\qquad\)对于这个最大方案的根，我们可以在\(DP\)的过程中顺便保存让\([l,r]\)区间加分最大的根节点\(g[l,r]\)，为了让字典序最小，我们让断点\(k\)从左向右扫描，遇到更大的值就要\(f[]和g[]\)一起更新，当值相同的时候，以\(k\)越小越好。
然后在输出的时候递归处理：
void print(int l, int r)
{
if (l > r) return ; // 不构成节点
int k = g[l][r]; // 根节点
printf("%d ", k);
print(l, k - 1), print(k + 1, r); // 分别递归左右子
}
代码
会贴两份，递推\(DP\)和记忆化搜索
递推DP
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50;
int f[N][N], g[N][N], n, w[N];
void print(int l, int r)
{
if (l > r) return ; // 不构成节点
int k = g[l][r]; // 根节点
printf("%d ", k);
print(l, k - 1), print(k + 1, r); // 分别递归左右子
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
memset(f, 0xcf, sizeof f);
for (int i = 1; i <= n; i ++ )
g[i][i] = i, f[i][i] = w[i]; // 长度为1的叶子节点分数和根的初始化
for (int len = 2; len <= n; len ++ ) //长度为1的初始化过了，从2开始
{
for (int l = 1, r = l + len - 1; r <= n; l ++, r ++ ) //枚举左端点和右端点
{
for (int k = l; k <= r; k ++ ) // 枚举断点
{
int &v = f[l][r], u, L, R;
L = (k == l) ? 1 : f[l][k - 1]; // 如果k == l代表没有左子树，左分数为1
R = (k == r) ? 1 : f[k + 1][r]; // 如果k == r代表没有右子树
u = L * R + w[k]; // 分数计算
if (u > v) v = u, g[l][r] = k; // 更新信息
}
}
}
printf("%d\n", f[1][n]);
print(1, n);
return 0;
}
记忆化搜索
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50;
int w[N], f[N][N], g[N][N], n;
int dp(int l, int r)
{
int &v = f[l][r];
if (~v) return v; // 算过的直接调用
if (l == r) return g[l][r] = l, f[l][r] = w[l]; // 叶子节点的处理
for (int k = l; k <= r; k ++ )
{
int u, L, R;
L = (k == l) ? 1 : dp(l, k - 1); // 如果k == l代表没有左子树，左分数为1
R = (k == r) ? 1 : dp(k + 1, r); // 右子同理
u = L * R + w[k];
if (u > v) g[l][r] = k, v = u;
}
return v;
}
void print(int l, int r)
{
if (l > r) return ;
int k = g[l][r];
printf("%d ", k);
print(l, k - 1), print(k + 1, r);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
memset(f, -1, sizeof f);
printf("%d\n", dp(1, n));
print(1, n);
return 0;
}