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

加分二叉树解题报告

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
加分二叉树解题报告_电脑基础知识_IT/计算机_专业资料。树型DP,动态规划20
加分二叉树.doc
加分二叉树_学科竞赛_高中教育_教育专区。基础算法,noip,noi,解题报告,搜索,动态规划,贪心,分治,数据结构 回专题模式 回学习阶段模式 【题目名称、来源】 加分二叉...
加分二叉树题解.doc
加分二叉树(树形动规)解题... 2页 1财富值 加分二叉树 20页 免费 NO
树型动态规划的实例分析(修改苹果树).pdf
节点构成的二叉树加分} root[i,i]:=i;{记录单个节点构成的二叉树的根节点...解题报告出自湖北省水果湖高中 伍先军写的第九届全国青少年信息学奥 林匹克联赛...
浅谈树型动态规划.doc
疑点是最大加分二叉树的前序遍历序列可能不唯一。 Ps:其实这题真正意义上来说还是一道普通的 dp 题目,但它批上了树的外表,所以都拿来 作对比和讨论, 解题报告...
信息学奥赛必读--二叉树与其应用_图文.ppt
信息学奥赛必读--二叉树与其应用 - 二叉树及其应用 雅礼 朱全民 二叉树 ? 二叉树是一种特殊的树型结构, ...
NOIP 2005-95 解题报告 北极天南星2005.doc
NOIP 2005 解题报告 北极天南星 2005-12-11 21:44:24 原创 1.谁拿了最多奖...3.加分二叉树(tree) 动态规划 二叉树的中序遍历具有一个很好的性质,就是点 ...
动态规划题目选讲_图文.ppt
时间复杂度:O(N^2) 例题二:加分二叉树 ? 设一个n个节点的二叉树tree
NOIP2003解题报告.pdf
NOIP2003解题报告_机械/仪表_工程科技_专业资料。NOIP2003解题报告 ...题三 【问题描述】 加分二叉树 第 5/10页 www.topschool.org 清北学堂金牌...
历年NOIP真题汇编(2000~2017)_图文.pdf
[4] P1038 神经网络 P1039 侦探推理 P1040 加分二叉树 P1
试题(树型动规).doc
试题(树型动规) - 树型动规专题 1.加分二叉树(binary.c/cpp)
树形动态规划.doc
疑点是最大加分二叉树的前序遍历序列可能不唯一。 Ps:其实这题真正意义上来说还是一道普通的 dp 题目,但它批上了树的外表,所以都拿来 作对比和讨论,解题报告...
状态表示&状态转移(进阶篇).doc
第 -8- 页共 9 页 3 衢州一中 胡承丰 五、 树形 DP: 题库: 加分二叉树(NOI、VIJOS) 选课(NOI、VIJOS) 这两道题网上的解题报告很多,我就不罗嗦了。 ...
动态规划_图文.pdf
解题步骤 ? 识别题目 ? 建立动态规划模型:写动态...(2000)规则类型动态规划 加分二叉树(2003)树型...动态规划法实验报告 暂无评价 2页 1下载券 动态规划...
动归例题.txt
动归例题 - 加分二叉树 【问题描述】 设一个n个节点的二叉树tree的中序遍历
动态规划3.doc
五、 题库: 题库: 加分二叉树(NOI、VIJOS) 选课(NOI、VIJOS) 这两道题网上的解题报告很多,我就不罗嗦了。 这两道题网上的解题报告很多,我就不罗嗦了。 ...
树形动态规划_图文.ppt
设f(i,j)中序遍历为i,i+1,…,j的二叉树的最大加分,则有: f(i,j
NOIP提高组 01-12 DP题目.doc
将上题的数据范围改成 6<n<=200000,2<=k<=100 03 加分二叉树 (binary.pas/dpr/c/cpp) 【问题描述】 设一个 n 个节点的二叉树 tree 的中序遍历为 (...
信息学奥赛树型动态规划的实例分析.doc
二,例题与解析 加分二叉树 【问题描述】 设一个 n 个节点的二叉树 tree 的...学奥林匹克联赛(N0IP2003)复赛提高组解题报告. Ural 1018 二*苹果树 题目 有...
NOIP2003提高组.pdf
试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树 tree。要求输出; (1)tree 的最高加分 (2)tree 的前序遍历 【输入格式】 第 1 行:一个整数...