题目描述
设一个 �n 个节点的二叉树 treetree 的中序遍历为(1,2,3,…,�)(1,2,3,…,n),其中数字 1,2,3,…,�1,2,3,…,n 为节点编号。每个节点都有一个分数(均为正整数),记第 �i 个节点的分数为 ��di,treetree 及它的每个子树都有一个加分,任一棵子树 subtreesubtree(也包含 treetree 本身)的加分计算方法如下:
subtreesubtree 的左子树的加分 ×× subtreesubtree 的右子树的加分 ++ subtreesubtree 的根的分数。
若某个子树为空,规定其加分为 11,叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为 (1,2,3,…,�)(1,2,3,…,n) 且加分最高的二叉树 treetree。要求输出
-
treetree 的最高加分。
-
treetree 的前序遍历。
输入格式
第 11 行 11 个整数 �n,为节点个数。
第 22 行 �n 个用空格隔开的整数,为每个节点的分数
输出格式
第 11 行 11 个整数,为最高加分(���≤4,000,000,000Ans≤4,000,000,000)。
第 22 行 �n 个用空格隔开的整数,为该树的前序遍历。
输入输出样例
输入 #1复制
5 5 7 1 2 10
输出 #1复制
145 3 1 2 4 5
说明/提示
数据规模与约定
对于全部的测试点,保证 1≤�<301≤n<30,节点的分数是小于 100100 的正整数,答案不超过 4×1094×109。
一道入门的区间dp,当然,根据写法不同你还可以把它归类为树形dp或者记忆化搜索,其实都无所谓啦。
作为一道入门题,我们完全可以“显然”地做出来,但是在这里还是想和大家回顾下动态规划以及区间动规。
Q:dp特点是什么?
A:dp把原问题视作若干个重叠的子问题的逐层递进,每个子问题的求解过程都会构成一个“阶段”,在完成一个阶段后,才会执行下一个阶段。
Q:dp要满足无后效性,什么叫无后效性?
A:已经求解的子问题不受后续阶段的影响。
有人觉得dp很抽象,那是因为没有一步一步来想,直接听别人的结论,我们在这里以这道题为例,一步一步来推导。
首先,我们要做的就是设计状态,其实就是设计dp数组的含义,它要满足无后效性。
关注这个 左子树*右子树+根 我只要知道左子树分数和右子树分数和根的分数(已给出),不就可以了吗?管他子树长什么样!
所以,我们�f数组存的就是最大分数,怎么存呢?
我们发现:子树是一个或多个节点的集合。
那么我们可不可以开一个�[�][�]f[i][j]来表示节点i到节点j成树的最大加分呢?可以先保留这个想法(毕竟暂时也想不到更好的了)。
如果这样话,我们就来设计状态转移方程。
按照刚刚的设计来说的话,我们的答案就是�[1][�]f[1][n]了,那么我们可以从小的子树开始,也就是len,区间长度。有了区间长度我们就要枚举区间起点,i为区间起点,然后就可以算出区间终点j。
通过加分二叉树的式子我们可以知道,二叉树的分取决于谁是根,于是我们就在区间内枚举根k。
特别的,�[�][�]=�[�]f[i][i]=a[i]其中a[i]为第i个节点的分数。
因为是要求最大值,所以我们就可以设计出
�[�][�]=���(�[�][�−1]∗�[�+1][�]+�[�][�])f[i][j]=MAX(f[i][k−1]∗f[k+1][j]+f[k][k])
于是乎,我们就自己设计出了一个dp过程,因为是顺着来的,所以很少有不成立的。文章来源:https://www.toymoban.com/news/detail-425793.html
至于输出前序遍历,我们再设计一个状态����[�][�]root[i][j]来表示节点i到节点j成树的最大加分所选的根节点。
所以我们按照根−>左−>右根−>左−>右的顺序递归输出即可。文章来源地址https://www.toymoban.com/news/detail-425793.html
代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 50;
typedef long long ll;
ll n;
ll f[MAXN][MAXN], root[MAXN][MAXN];
void print(ll l, ll r) {
if (l > r)return;
printf("%lld ", root[l][r]);
if (l == r)return;
print(l, root[l][r] - 1);
print(root[l][r]+1,r);
}
int main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++)scanf("%lld", &f[i][i]),f[i][i-1]=1, root[i][i] = i;
for (int len = 1; len < n; ++len) {
for (int i = 1; i + len <= n; ++i) {
int j = i + len;
f[i][j] = f[i + 1][j] + f[i][i];//默认它的左子树为空,如果有的话,这肯定不是最优解
root[i][j] = i;//默认从起点选根
for (int k = i + 1; k < j; ++k) {
if (f[i][j] < f[i][k - 1] * f[k + 1][j] + f[k][k]) {
f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k];
root[i][j] = k;
}
}
}
}
cout << f[1][n] << endl;
print(1, n);
return 0;
}
到了这里,关于P1040 [NOIP2003 提高组] 加分二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!