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.



更多相关文章:
二叉树
加分二叉树 20页 免费 二叉树 5页 1下载券 二叉树 3页 2下载券 二叉树 2...立​二​叉​树​,​并​对​树​进​行​操​作​ ​...
BinaryTree 二叉树
二叉树的应用研究 6页 2财富值 加分二叉树 20页 免费喜欢此文档的还喜欢 ...数据结构 C语言源程序和说明 二叉树数据结构 C语言源程序和说明 二叉树隐藏>>...
树型动态规划的实例分析(完美整理)
如果用数组 value[i,j]表示从节点 i 到节点 j 所组 分析 成的二叉树的最大加分,则动态方程可以表示如下: value[i,j]=max{value[i,i]+value[i+1,j]...
NOIP2012信息学奥林匹克竞赛初赛-模拟卷
试求一棵符合中序遍历为(1,2,3,?,n)且加分最高的二叉树 tree。要求输出; (1)tree 的最高加分 (2)tree 的前序遍历 var n,i,j,k,l:integer; p:...
树形动规
苹果二叉树是以枝条的保留数, 苹果二叉树是以枝条的保留数, 加分二叉树是 对于左右儿子的判定, 对于左右儿子的判定, 上面两题是树形动规的基础题目, 三色二叉 ...
深入分析区间型动态规划
加分二叉树---NOIP2003 4. 最优排序二叉树--- CTSC96 这些题目出现的频次及其所在比赛的重要性足以说明区间型动态规划在各类动态规划中有 着举足轻重的地位。 ...
DP Summary
树型动态规划 1 ---加分二叉树 (从两侧到根结点模型) F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]} 12. 树型动态规划 2 ---选课 (多叉树转二叉...
100个动规方程
---加分二叉树 (从两侧到根结点模型) F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]} 树型动态规划 2 12. ---选课 (多叉树转二叉树,自顶向下模型...
100种DP方程
树型动态规划 1 ---加分二叉树 (从两侧到根结点模型) F[I,j]:=max{f[...[I,0]:=1 57 树形动态规划 ---有向树 k 中值问题 F[I,r,k]:=max...
百题DP大总结
树型动态规划 1 ---加分二叉树 (从两侧到根结点模型 从两侧到根结点模型) ...[I,0]:=1 57 树形动态规划 ---有向树 k 中值问题 有向树 F[I,r,k...
更多相关标签:
二叉树    二叉树遍历    加分二叉树 动态规划    加分二叉树pascal    apt-get install    加分二叉树 题解    加分二叉树 c++    加分二叉树 oj    

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

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