9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

加分二叉树



回专题模式 回学习阶段模式 【题目名称、来源】 加分二叉树 noip2003t3 【问题描述】 设一个 n 个节点的二叉树 tree 的中序遍历为(l,2,3,…,n) ,其中数字 1,2,3,…,n 为节点编 号。每个节点都有一个分数(均为正整数) ,记第 j 个节点的分数为 di,tree 及它的每个子 树都有一个加分,任一棵子树 subtree(也包含 tree 本身)的加分计算方法如下: subtree 的左子树的加分× subtree 的右子树的加分+subtree 的根的分数 若某个子树为空,规定其加分为 1,叶子的加分就是叶节点本身的分数。不考虑它的空 子树。 试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树 tree。要求输出; (1)tree 的最高加分 (2)tree 的前序遍历 【输入格式】 第 1 行:一个整数 n(n<30) ,为节点个数。 第 2 行:n 个用空格隔开的整数,为每个节点的分数(分数<100) 。 【输出格式】 第 1 行:一个整数,为最高加分(结果不会超过 4,000,000,000) 。 第 2 行:n 个用空格隔开的整数,为该树的前序遍历。 【输入样例】 5 5 7 1 2 10 【输出样例】 145 31245

【所属专题】 动态规划 【适合学习阶段】 第二阶段 【解题思路】 问题分析: 这个问题类似于矩阵最小乘积,设 c[i,j]代表序列 i..j 构成的二叉树子树的最大加分值, 所以很明显状态转移方程为 c[i,j]=max{c[i,k-1]*c[k+1,j]+a[k],其中 i<=k<=j, a[k]为输入的节点加分}即以 k 为根的加 分二叉树的值中取最大的。 因为还要求出先序遍历序列,所以需要记录 root[i,j],即 i..j 取得最大加分时的根是谁。 不需要建立树结构,根据 root[i,j]就可以递归求出先序遍历序列。

注意初始条件: 当 l=1 时,即只有一个节点时 c[i,i]=a[i],root[i]=i 当 l=2 时,即只有两个节点时,为了保持中序遍历顺序,只能以第一个节点为根节点, 所以 c[i,i+1]=a[i]+a[i+1]*1=a[i]+a[i+1],root[i,i+1]=i; 存储结构: 【测试数据】 【源程序】 program tree;{noip2003 加分二叉树} var zuo,you:comp;{左右子树的加分} jiafen:array[1..30,1..30]of comp; {jiafen[i,j]代表从 i 到 j 的节点最大加分值} xianxu:array[1..30,1..30]of integer; {xianxu[i,j]代表从 i 到 j 的节点取得最大加分值的根节点编号} zhi:array[1..30]of integer;{节点原始加分} i,j,k,l,n:integer; procedure bianli(i,j:integer);{先序遍历} begin if i<j then begin write(xianxu[i,j],' '); bianli(i,xianxu[i,j]-1); bianli(xianxu[i,j]+1,j); end else if j=i then write(xianxu[i,j],' ') end; begin assign(input,'tree.in'); reset(input); readln(n); for i:=1 to n do read(zhi[i]); close(input); fillchar(jiafen,sizeof(jiafen),0); fillchar(xianxu,sizeof(xianxu),0); {初始化 l=1,2 时加分和树根} for i:=1 to n do begin jiafen[i,i]:=zhi[i]; xianxu[i,i]:=i; end; for i:=1 to n-1 do begin jiafen[i,i+1]:=jiafen[i,i]+jiafen[i+1,i+1]; xianxu[i,i+1]:=i;

end; {动态规划,递推求出 jiafen[i,j]} for l:=3 to n do for i:=1 to n-l+1 do begin j:=i+l-1; for k:=i to j do begin if k=i then zuo:=1 else zuo:=jiafen[i,k-1]; if j=k then you:=1 else you:=jiafen[k+1,j]; if jiafen[i,j]<zuo*you+zhi[k] then begin jiafen[i,j]:=zuo*you+zhi[k]; xianxu[i,j]:=k; end; end; end; assign(output,'tree.out'); rewrite(output); writeln(jiafen[1,n]:0:0); bianli(1,n); close(output); end.



更多相关文章:
加分二叉树(树形动规)解题报告
加分二叉树(树形动规)解题报告_简历封面/模板_求职/职场_应用文书。加分二叉树(树形动规)解题报告描述Description 设一个n个节点的二叉树 个节点的二叉树tree的中...
加分二叉树题解
加分二叉树时间限制(普通/Java):1000MS/10000MS 总提交:234 描述 设一个 n 个节点的二叉树 tree 的中序遍历为(l,2,3,…,n),其中数字 1,2,3,…,n 为...
树型动态规划的实例分析(完美整理)
如果用数组 value[i,j]表示从节点 i 到节点 j 所组 分析 成的二叉树的最大加分,则动态方程可以表示如下: value[i,j]=max{value[i,i]+value[i+1,j]...
二叉树
加分二叉树 20页 免费 二叉树 5页 1下载券 二叉树 3页 2下载券 二叉树 2...【问题描述】 现需要编写一套二叉树的操作函数,以便用户能够方便的利用这些函数...
二叉树检索
加分二叉树 20页 免费 二叉树 5页 1下载券二​叉​树​检​索 ...输出最小生成树的权值。 最短路(SPFA 算法) #include <stdio.h> #include <...
二叉树
加分二叉树 20页 免费 二叉树 5页 1下载券 二叉树 3页 2下载券 第6章 二叉...二叉树 汪碧霞 11 级软件技术(2)班 汪红霞 2012-12 信息工程学院 信息科学...
二叉树
加分二叉树 20页 免费 二叉树 5页 1下载券 二叉树 3页 2下载券 二叉树 2...一、 实验目的 1.掌握二叉树的存储实现方法。 2.掌握二叉树的基本操作:建立...
附录二叉树
完全二叉树 2页 5财富值 二叉树的的实现 16页 5财富值 二叉树实现 3页 1财富值 第六章(二叉树) 95页 免费 二叉树的应用研究 6页 2财富值 加分二叉树 ...
BinaryTree 二叉树
二叉树的应用研究 6页 2财富值 加分二叉树 20页 免费喜欢此文档的还喜欢 ...数据结构 C语言源程序和说明 二叉树数据结构 C语言源程序和说明 二叉树隐藏>>...
树形动规
苹果二叉树是以枝条的保留数, 苹果二叉树是以枝条的保留数, 加分二叉树是 对于左右儿子的判定, 对于左右儿子的判定, 上面两题是树形动规的基础题目, 三色二叉 ...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图