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.


赞助商链接

更多相关文章:
加分二叉树
加分二叉树_IT/计算机_专业资料。同类问题:Ural 1018 二*苹果树 Tju1053 技能树 Ural 1039 战略游戏 选课 没有上司的晚会 《思考一》 加分二叉树 【问题描述】...
树型动态规划的实例分析(完美整理)
如果用数组 value[i,j]表示从节点 i 到节点 j 所组 分析 成的二叉树的最大加分,则动态方程可以表示如下: value[i,j]=max{value[i,i]+value[i+1,j]...
加分二叉树题解
加分二叉树时间限制(普通/Java):1000MS/10000MS 总提交:234 描述 设一个 n 个节点的二叉树 tree 的中序遍历为(l,2,3,…,n),其中数字 1,2,3,…,n 为...
二叉树
加分二叉树 20页 免费 二叉树 5页 1下载券 二叉树 3页 2下载券 二叉树 2...【问题描述】 现需要编写一套二叉树的操作函数,以便用户能够方便的利用这些函数...
二叉树
加分二叉树 20页 免费 二叉树 5页 1下载券 二叉树 3页 2下载券 第6章 二叉...数据结构课程设计 求二叉树上结点的路径 bintree createbintree(bintree bt) ...
二叉树
加分二叉树 20页 免费 二叉树 5页 1下载券 二叉树 3页 2下载券 二叉树 2...一、 实验目的 1.掌握二叉树的存储实现方法。 2.掌握二叉树的基本操作:建立...
树形动态规划
如果用数组 value[i,j]表示从节点 i 到节点 j 所组 分析 成的二叉树的最大加分,则动态方程可以表示如下: value[i,j]=max{value[i,i]+value[i+1,j]...
树形动规
苹果二叉树是以枝条的保留数, 苹果二叉树是以枝条的保留数, 加分二叉树是 对于左右儿子的判定, 对于左右儿子的判定, 上面两题是树形动规的基础题目, 三色二叉 ...
信息学奥赛——树型动态规划的实例分析
二,例题与解析 加分二叉树 【问题描述】 设一个 n 个节点的二叉树 tree 的中序遍历为(l,2,3,…,n),其中数字 1,2,3,…,n 为节点编号.每个节点都有一...
历年NOIP(普及组提高组)试题难度列表
加分二叉树 传染病控制 津津的储蓄计划 合并果子 合唱队形 虫食算 谁拿了最多奖学金 过河 篝火晚会 等价表达式 能量项链 金明的预算方案 作业调度方案 2^k ...
更多相关标签:

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

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