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 战略游戏 选课 没有上司的晚会 《思考一》 加分二叉树 【问题描述】...
加分二叉树
回专题模式 回学习阶段模式 【题目名称、来源】 加分二叉树 noip2003t3 【问题描述】 设一个 n 个节点的二叉树 tree 的中序遍历为(l,2,3,…,n) ,其中...
加分二叉树解题报告
加分二叉树解题报告_电脑基础知识_IT/计算机_专业资料。树型DP,动态规划2014.8.19 加分二叉树【NOIP2003 提高组】 Description 设一个 n 个节点的二叉树 tree ...
更多相关标签:
二叉树    二叉树遍历    加分二叉树 动态规划    加分二叉树pascal    apt-get install    加分二叉树 题解    加分二叉树 c++    加分二叉树 oj    

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

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