【题目来源】
洛谷：P1040 [NOIP 2003 提高组] 加分二叉树 - 洛谷
【题目描述】
设一个 \(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。要求输出
- tree 的最高加分。
- tree 的前序遍历。
【输入】
第 \(1\) 行 \(1\) 个整数 \(n\)，为节点个数。
第 \(2\) 行 \(n\) 个用空格隔开的整数，为每个节点的分数
【输出】
第 \(1\) 行 \(1\) 个整数，为最高加分（\(Ans≤4,000,000,000\)）。
第 \(2\) 行 \(n\) 个用空格隔开的整数，为该树的前序遍历。
【输入样例】
5
5 7 1 2 10
【输出样例】
145
3 1 2 4 5
【算法标签】
《洛谷 P1040 加分二叉树》 #动态规划DP# #递归# #区间DP# #NOIP提高组# #2003# #Special judge# #O2优化#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long // 定义int为long long类型const int N = 35; // 定义最大节点数
int n; // 二叉搜索树的节点数量
int d[N]; // 存储每个节点的权值
int f[N][N]; // DP数组，f[i][j]表示区间[i,j]构成BST的最大分数
int root[N][N]; // 记录区间[i,j]的根节点位置// 前序遍历输出BST结构
void dfs(int x, int y)
{// 当区间长度为1时直接输出if (x == y){cout << x << ' ';return;}// 区间不合法时返回if (x > y) return;// 输出当前区间的根节点cout << root[x][y] << ' ';// 递归遍历左子树dfs(x, root[x][y] - 1);// 递归遍历右子树dfs(root[x][y] + 1, y);
}signed main() // 使用signed替代int（因为定义了int为long long）
{// 输入节点数量cin >> n;// 输入每个节点的权值并初始化DP数组for (int i = 1; i <= n; i++){cin >> d[i];f[i][i] = d[i]; // 单个节点的分数就是其权值}// 动态规划处理所有区间for (int len = 2; len <= n; len++) // 枚举区间长度{for (int i = 1; i + len - 1 <= n; i++) // 枚举区间起点{int j = i + len - 1; // 计算区间终点// 情况1：i作为根节点f[i][j] = f[i][i] + f[i + 1][j];root[i][j] = i;// 情况2：j作为根节点int t = f[i][j - 1] + f[j][j];if (t > f[i][j]){f[i][j] = t;root[i][j] = j;}// 情况3：k作为根节点（i < k < j）for (int k = i + 1; k < j; k++){t = f[i][k - 1] * f[k + 1][j] + f[k][k];if (t > f[i][j]){f[i][j] = t;root[i][j] = k;}}}}// 输出最大分数cout << f[1][n] << endl;// 前序遍历输出BST结构dfs(1, n);return 0;
}
【运行结果】
5
5 7 1 2 10
145
3 1 2 4 5