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

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

题目描述

设一个 �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。要求输出

  1. treetree 的最高加分。

  2. 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过程,因为是顺着来的,所以很少有不成立的。

至于输出前序遍历,我们再设计一个状态����[�][�]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模板网!

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

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

相关文章

  • 加分二叉树

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

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

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

    2024年02月06日
    浏览(32)
  • 二叉树题目:对称二叉树

    标题:对称二叉树 出处:101. 对称二叉树 3 级 要求 给你一个二叉树的根结点 root texttt{root} root ,检查它是否轴对称。 示例 示例 1: 输入: root   =   [1,2,2,3,4,4,3] texttt{root = [1,2,2,3,4,4,3]} root = [1,2,2,3,4,4,3] 输出: true texttt{true} true 示例 2: 输入: root   =   [1,2,2,null,3,null,

    2024年02月12日
    浏览(34)
  • 二叉树题目:二叉树的中序遍历

    标题:二叉树的中序遍历 出处:94. 二叉树的中序遍历 3 级 要求 给你二叉树的根结点 root texttt{root} root ,返回其结点值的中序遍历。 示例 示例 1: 输入: root   =   [1,null,2,3] texttt{root = [1,null,2,3]} root = [1,null,2,3] 输出: [1,3,2] texttt{[1,3,2]} [1,3,2] 示例 2: 输入: root   =  

    2024年02月09日
    浏览(50)
  • 二叉树题目:在二叉树中增加一行

    标题:在二叉树中增加一行 出处:623. 在二叉树中增加一行 5 级 要求 给定一个二叉树的根结点 root texttt{root} root 和两个整数 val texttt{val} val 和 depth texttt{depth} depth ,在给定的深度 depth texttt{depth} depth 处添加一行值为 val texttt{val} val 的结点。 注意,根结点 root texttt{root}

    2024年02月06日
    浏览(32)
  • 二叉树题目:二叉树的层序遍历 II

    标题:二叉树的层序遍历 II 出处:107. 二叉树的层序遍历 II 4 级 要求 给你二叉树的根结点 root texttt{root} root ,返回其结点值自底向上的层序遍历(即从左到右,按从叶结点所在层到根结点所在层逐层遍历)。 示例 示例 1: 输入: root   =   [3,9,20,null,null,15,7] texttt{root = [3

    2024年02月11日
    浏览(35)
  • 【二叉树复习】C++ 二叉树复习及题目解析 (1)

    目录 二叉树 树 相关概念 树的表示 二叉树 概念 存储结构 小练习 树题目: leetcode 965 单值二叉树。 leetcode 103. 二叉树的最大深度 leetcode 226 翻转二叉树 leetcode100 相同的树 leetcode 101 对称二叉树 leetcode 144前序遍历 94 中序遍历 145 后序遍历 leetcode 572 另一棵树的子树 本文将从二

    2024年02月12日
    浏览(31)
  • 二叉树经典算法题目

    省略 输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。 例如: 给定二叉树 [3,9,20,null,null,15,7] , 返回它的最大深度 3 。 思路:递归,当前数的深度等于左子数和右子树其中最大深

    2024年02月09日
    浏览(55)
  • 二叉树题目合集(C++)

    链接: 二叉树创建字符串 题目要求: PS :题目描述的不是特别清楚,其实就是 前序遍历 树,然后 用括号分别包含左子树和右子树遍历结果 。 基础思路: (1)不考虑括号去重 的话,其实只要 访问完当前节点后递归访问左右子树 即可,并且在访问前加左括号,访问完毕后

    2024年02月07日
    浏览(30)
  • 二叉树基础oj题目

    前文中,介绍了二叉树的基本概念及基础操作,进一步对于二叉树的递归遍历及子问题的处理思想有了一定的了解。本文将带来几道二叉树经典的oj题目。 对称二叉树 平衡二叉树 二叉树的层序遍历 leetcode题目链接 题目描述:给你一个二叉树的根节点 root , 检查它是否轴对称

    2024年01月21日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包