加分二叉树

这篇具有很好参考价值的文章主要介绍了加分二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

设一个 \(n\) 个节点的二叉树 \(\text{tree}\) 的中序遍历为\((1,2,3,\ldots,n)\),其中数字 \(1,2,3,\ldots,n\) 为节点编号。每个节点都有一个分数(均为正整数),记第 \(i\) 个节点的分数为 \(d_i\)\(\text{tree}\) 及它的每个子树都有一个加分,任一棵子树 \(\text{subtree}\)(也包含 \(\text{tree}\) 本身)的加分计算方法如下:

\(\text{subtree}\) 的左子树的加分 \(\times\) \(\text{subtree}\) 的右子树的加分 \(+\) \(\text{subtree}\) 的根的分数。

若某个子树为空,规定其加分为 \(1\),叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为 \((1,2,3,\ldots,n)\) 且加分最高的二叉树 \(\text{tree}\)。要求输出

  1. \(\text{tree}\) 的最高加分。

  2. \(\text{tree}\) 的前序遍历。

输入格式

\(1\)\(1\) 个整数 \(n\),为节点个数。

\(2\)\(n\) 个用空格隔开的整数,为每个节点的分数

输出格式

\(1\)\(1\) 个整数,为最高加分($ Ans \le 4,000,000,000$)。

\(2\)\(n\) 个用空格隔开的整数,为该树的前序遍历。

样例 #1

样例输入 #1

5
5 7 1 2 10

样例输出 #1

145
3 1 2 4 5

提示

数据规模与约定

对于全部的测试点,保证 \(1 \leq n< 30\),节点的分数是小于 \(100\) 的正整数,答案不超过 \(4 \times 10^9\)

题目分析

加分二叉树文章来源地址https://www.toymoban.com/news/detail-456563.html

代码实现

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=55;
//dp[i][j]表示中序遍历为i~j的树的最大分值 
//mid[i][j]表示中序遍历为i~j的树的根节点 
int dp[N][N],score[N],mid[N][N];
void dfs(int l,int r){
	if(l>r)return;
	int root=mid[l][r];
	cout<<root<<" ";
	dfs(l,root-1);
	dfs(root+1,r);
}
signed main(){
	int n,res;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>score[i];	
	//枚举区间长度
	for(int len=1;len<=n;len++){
		//枚举左端点
		for(int l=1;l+len-1<=n;l++){
			//右端点
			int r=l+len-1;
			//枚举中序遍历的根节点
			for(int k=l;k<=r;k++){
				int left=0,right=0;
				//如果没有左子树,则左子树其加分为1 
				if(k==l)left=1;
				//否则其左子树加分为dp[l][k-1] 
				else left=dp[l][k-1];
				//如果没有右子树, 则右子树其加分为1
				if(k==r)right=1;
				//否则其左子树加分为dp[k+1][r] 
				else right=dp[k+1][r];
				int res=left*right+score[k];
				//如果左子树和右子树都没有,则其加分就是叶节点本身的分数 
				if(l==r)res=score[k];
				//如果加分大于当前dp[l][r],则更新dp[l][r],并记录中序遍历为l~r的树的根节点 
				if(res>dp[l][r]){
					dp[l][r]=res;
					mid[l][r]=k;
				}
			} 
		} 
	} 
	cout<<dp[1][n]<<endl;
	dfs(1,n);
	return 0;
}

到了这里,关于加分二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [NOIP2003 提高组] 加分二叉树

    设一个 n 个节点的二叉树 tree 的中序遍历为(1,2,3,…,n),其中数字 1,2,3,…,n 为节点编号。每个节点都有一个分数(均为正整数),记第 i 个节点的分数为 di​,tree 及它的每个子树都有一个加分,任一棵子树 subtree(也包含 tree 本身)的加分计算方法如下: subtree 的左子

    2024年02月08日
    浏览(41)
  • 寻找二叉树一个节点的后继节点

    后继节点:中序遍历的后一个节点 普通二叉树:中序遍历得到一个list,时间复杂度O(n) 本题的二叉树:有父节点的指针,后继节点与原节点的距离为1, 因此可以直接通过父节点找到下一个节点 优化:节点到另一个节点的真实距离为k,时间复杂度为O(k) 情况分析: 情况一:

    2024年02月08日
    浏览(34)
  • P1040 [NOIP2003 提高组] 加分二叉树

    设一个 �n 个节点的二叉树 treetree 的中序遍历为(1,2,3,…,�)(1,2,3,…,n),其中数字 1,2,3,…,�1,2,3,…,n 为节点编号。每个节点都有一个分数(均为正整数),记第 �i 个节点的分数为 ��di​,treetree 及它的每个子树都有一个加分,任一棵子树 subtreesubtree(也包含 t

    2023年04月26日
    浏览(43)
  • luogu_P1040 [NOIP2003 提高组] 加分二叉树

    P1040 [NOIP2003 提高组] 加分二叉树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题意:给你一颗中序遍历为1到n的二叉树,和每个节点的val。树的值=左子树的值×右子树的值+根的val,空树值为1,求整个树最大值和这个值树的前序遍历。 题解:区间dp。dp[l][r]表示最大值,root[l][

    2023年04月27日
    浏览(77)
  • 二叉树:填充每个节点的下一个右侧节点指针(java)

    116题:填充每个节点的下一个右侧节点指针 给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下: 填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。 初始状态下

    2024年02月07日
    浏览(39)
  • C++---区间DP---加分二叉树(每日一道算法2023.4.28)

    题目: 设一个 n 个节点的二叉树 tree 的中序遍历为(1,2,3,…,n),其中数字 1,2,3,…,n 为节点编号。 每个节点都有一个分数(均为正整数),记第 i 个节点的分数为 di,tree 及它的每个子树都有一个加分,任一棵子树 subtree(也包含 tree 本身)的加分计算方法如下: subtree的左

    2024年02月06日
    浏览(33)
  • 随想录刷题笔记 —二叉树篇3 117填充每个节点的下一个右侧节点指针II 104二叉树最大深度 111二叉树最小深度

    和116的区别在于116是完美二叉树,而117中的结点并非左右子结点都存在。 解法一:队列 解法二:双循环代替队列 解法一:队列 使用depth标记深度,进行层序遍历,每遍历完一层,depth+1 解法二:递归 递归出口:传入结点为空,返回0 否则返回左子结点和右子结点返回值的最

    2024年02月19日
    浏览(45)
  • 【力扣 - 二叉树的中序遍历】

    给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 树中节点数目在范围 [0, 100] 内 首先我们需要了解什么是二叉树的中序遍历:按照访问左子树——根节点——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候我们按照同样的方式遍历,直到遍历完整棵树。因

    2024年02月22日
    浏览(40)
  • 根据二叉树的先序、中序、后序遍历构建二叉树-图文详解

    引言:根据一颗二叉树,可以得出他的先序、中序、后序三种遍历方式,那么如果我们知道了他的前序、中序、后序遍历,如何绘制出这颗二叉树呢? 特性A,对于前序遍历,第⼀个肯定是根节点; 特性B,对于后序遍历,最后⼀个肯定是根节点; 特性C,利⽤前序或后序遍历

    2024年02月06日
    浏览(44)
  • 【树】建立二叉链表存储的二叉树+遍历二叉树(先序、中序、后序、层序)

    二叉树的构建利用了递归的原理,在按先序序列构建二叉树时,为了能让电脑知道每个结点是否有左右孩子,我们要对原二叉树进行 扩展 ,明确表示每个结点的左右孩子,若当前结点没有左右孩子,我们用’#\\\'表示。 由普通二叉树----扩展二叉树,如下图: 此时当我们按先序

    2024年02月07日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包