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 为...
二叉树
加分二叉树 20页 免费 二叉树 5页 1下载券 二叉树 3页 2下载券 二叉树 2...【问题描述】 现需要编写一套二叉树的操作函数,以便用户能够方便的利用这些函数...
浅谈树型动态规划
如果用数组 value[i,j]表示从节点 i 到节点 j 所组 成的二叉树的最大加分,则动态方程可以表示如下: value[i,j]=max{value[i,i]+value[i+1,j],value...
二叉树
加分二叉树 20页 免费 二叉树 5页 1下载券 二叉树 3页 2下载券 第6章 二叉...假设某二叉树的先序遍历序列是 abdgcefh,中序遍历序列是 dgbaechf,画出二 叉...
二叉树
加分二叉树 20页 免费 二叉树 5页 1下载券 二叉树 3页 2下载券 第6章 二叉...二叉树 山东工商学院计算机科学与技术学院 张雪姣 自然概率和风险中性 风险中性的...
二叉树
加分二叉树 20页 免费 二叉树 5页 1下载券 二叉树 3页 2下载券 二叉树 2...二叉查找树二叉查找树(Binary Search Tree),或者是一颗空树,或者是具有下列性质...
二叉树
加分二叉树 20页 免费 二叉树 5页 1下载券 二叉树 3页 2下载券 二叉树 2...{ //用指针 newpointer 初始化二叉搜索树树根,赋值实现 Initialize(newpointer)...
二叉树
加分二叉树 20页 免费 二叉树 5页 1下载券 二叉树 3页 2下载券 二叉树 2...一、 实验目的 1.掌握二叉树的存储实现方法。 2.掌握二叉树的基本操作:建立...
tree
10118 - 加分二叉树 Time Limit: 1000MS Memory Limit: 32768KB 【问题描述】 设一个 n 个节点的二叉树 tree 的中序遍历为(l,2,3,…,n),其中数字 1,2...
更多相关标签:

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

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