当前位置:首页 >> 电脑基础知识 >>

加分二叉树解题报告


2014.8.19

加分二叉树【NOIP2003 提高组】 Description
设一个 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 的前序遍历

Input
第 1 行:一个整数 n(n < 30),为节点个数。 第 2 行:n 个用空格隔开的整数,为每个节点的分数(分数 < 100)。

Output
第 1 行:一个整数,为最高加分(结果不会超过 4,000,000,000)。 第 2 行:n 个用空格隔开的整数,为该树的前序遍历。

Sample Input
5 5 7 1 2 10

Sample Output
145 3 1 2 4 5

题型:树型动规

用递归遍历整棵树。因为给出的是中序遍历,要求求出前序,所以实际上是区间动规。 在读入数据时把 ans[i][i]初始化为 i 的分数,表示当一棵子树中只有一个节点时的加分。 把 ans[i-1][i]初始化为 i 与 i-1 分数之和,root[i-1][i]为 i-1(这点很重要!因为有多解,所以 只有这样才能和标准输出一样) 。 枚举每一个节点 k 作为根节点,递归查找 f(I,k-1)*f(k+1,j)+score[k],保存最大值为 max 和 k。 结束循环时,ans[i][j]=max,root[i][j]=k; 最后递归输出即可。 代码: (变量名稍有不同) #include<iostream> using namespace std; long ans[40][40],root[40][40],map[40]={0},n; long dfs(long x,long y) { long s,sa,sb,an=0,w; for(s=x;s<=y;s++){ if(x<=s-1 && s+1<=y){ if(ans[x][s-1]>=0)sa=ans[x][s-1]; else sa=dfs(x,s-1); if(ans[s+1][y]>=0)sb=ans[s+1][y]; else sb=dfs(s+1,y); if(sa*sb+map[s]>an){ an=sa*sb+map[s]; w=s; } } } ans[x][y]=an; root[x][y]=w; return an; } void out(long x,long y) { if(root[x][y]!=0){ cout<<root[x][y]<<' '; if(x!=y){ out(x,root[x][y]-1); out(root[x][y]+1,y); } } } int main() { long s; cin>>n;

memset(ans,-1,sizeof(ans)); for(s=1;s<=n;s++){ cin>>map[s]; ans[s][s]=map[s]; root[s][s]=s; ans[s-1][s]=map[s]+map[s-1]; root[s-1][s]=s-1; } cout<<dfs(1,n); cout<<endl; out(1,n); } By 逸仔


相关文章:
加分二叉树.doc
加分二叉树_学科竞赛_高中教育_教育专区。基础算法,noip,noi,解题报告,搜索,动态规划,贪心,分治,数据结构 回专题模式 回学习阶段模式 【题目名称、来源】 加分二叉...
NOIP2003解题报告.pdf
NOIP2003解题报告_机械/仪表_工程科技_专业资料。NOIP2003解题报告 ...题三 【问题描述】 加分二叉树 第 5/10页 www.topschool.org 清北学堂金牌...
NOIP 2005-95 解题报告 北极天南星2005.doc
NOIP 2005 解题报告 北极天南星 2005-12-11 21:44:24 原创 1.谁拿了最多奖...3.加分二叉树(tree) 动态规划 二叉树的中序遍历具有一个很好的性质,就是点 ...
信息学奥赛树型动态规划的实例分析.doc
二,例题与解析 加分二叉树 【问题描述】 设一个 n 个节点的二叉树 tree 的...学奥林匹克联赛(N0IP2003)复赛提高组解题报告. Ural 1018 二*苹果树 题目 有...
动态规划总结.doc
第 -8- 页共 9 页 3 石家庄二中 贾志豪 五、 树形 DP: : 题库: 题库: 加分二叉树(NOI、VIJOS) 选课(NOI、VIJOS) 这两道题网上的解题报告很多,我就不...
树形动态规划.doc
疑点是最大加分二叉树的前序遍历序列可能不唯一。 Ps:其实这题真正意义上来说还是一道普通的 dp 题目,但它批上了树的外表,所以都拿来 作对比和讨论,解题报告...
树型动态规划的实例分析(修改苹果树).pdf
节点构成的二叉树加分} root[i,i]:=i;{记录单个节点构成的二叉树的根节点...解题报告出自湖北省水果湖高中 伍先军写的第九届全国青少年信息学奥 林匹克联赛...
动态规划3.doc
五、 题库: 题库: 加分二叉树(NOI、VIJOS) 选课(NOI、VIJOS) 这两道题网上的解题报告很多,我就不罗嗦了。 这两道题网上的解题报告很多,我就不罗嗦了。 ...
状态表示&状态转移(进阶篇).doc
第 -8- 页共 9 页 3 衢州一中 胡承丰 五、 树形 DP: 题库: 加分二叉树(NOI、VIJOS) 选课(NOI、VIJOS) 这两道题网上的解题报告很多,我就不罗嗦了。 ...
浅谈树型动态规划.doc
疑点是最大加分二叉树的前序遍历序列可能不唯一。 Ps:其实这题真正意义上来说还是一道普通的 dp 题目,但它批上了树的外表,所以都拿来 作对比和讨论, 解题报告...
浅谈树型动态规划.doc
疑点是最大加分二叉树的前序遍历序列可能不唯一。 Ps:其实这题真正意义上来说还是一道普通的 dp 题目,但它批上了树的外表,所以都 拿来作对比和讨论,解题报告...
高中信息技术 全国青少年奥林匹克联赛教案 树型动态规....doc
疑点是最大加分二叉树的前序遍历序列可能不唯一。 Ps:其实这题真正意义上来说还是一道普通的 dp 题目,但它批上了树的外表,所以都拿 来作对比和讨论,解题报告...
Noip试题分析.ppt
NOIP2000-2009提高组解题报... 47页 5财富值 NOIP2010第十六届初赛试题... ...加分二叉树:树型动态规划,树的遍历 加分二叉树: 加分二叉树 树型动态规划, 4...
NOIP提高组 01-12 DP题目.doc
将上题的数据范围改成 6<n<=200000,2<=k<=100 03 加分二叉树 (binary.pas/dpr/c/cpp) 【问题描述】 设一个 n 个节点的二叉树 tree 的中序遍历为 (...
动态规划题目选讲_图文.ppt
时间复杂度:O(N^2) 例题二:加分二叉树 ? 设一个n个节点的二叉树tree
信息学奥赛必读--二叉树与其应用_图文.ppt
信息学奥赛必读--二叉树与其应用 - 二叉树及其应用 雅礼 朱全民 二叉树 ? 二叉树是一种特殊的树型结构, 它的特点是每个节点至多只有两 个子节点。 ? 二叉树...
!联赛试题分类解析之动态规划篇.doc
5. 加分二叉树(NOIP2003) 【问题描述】 设一个 n 个节点的二叉树
NOIP总结选编.doc
暂时放在这里吧) 加分二叉树(2003)DP,很好的 DP,涉及树; (★★★) 传染病...。 后来看了解题报告。 。太绝了。 。。 首先:第一个动态规划是计算答案的:...
task2.doc
task2 - NOIp2003 题目名称 神经网络 侦探推理 加分二叉树 传染
20141010冲刺NOIP模拟测试11.doc
答案是:左子树的根节点是作为根时能够让左子树得分最大的节点,右子树的根节点是作为根时能够 让右子树得分最大的节点。 那么加分二叉树的最优子结构可以表述如...