加分二叉树解题报告

1、2014. & 19加分义树【0IP2003提高组】Description设一个n个节点的二叉树tree的中序遍历为(1, 2, 3,n),其中数字 l,2,3,n为节点编号。每个节点都有一个分数(均为正整数)，记第j个节点的分 数为di, tree及它的每个子树都有一个加分，任一棵子树subtree(也包含tree本 身)的加分计算方法如下：subtree的左子树的加分X subtree的右子树的加分+subtree的根的分数若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。不考 虑它的空子树。试求一棵符合中序遍历为(1,2, 3,n)且加分最高的二义树tree。要求输

2、出:(1) tree的最高加分(2) tree的前序遍历Input第1行:一个整数n(n <30),为节点个数。第2行:n个用空格隔开的整数，为每个节点的分数(分数100)。Output第1行:一个整数，为最高加分(结果不会超过4, 000, 000, 000) o第2行:n个用空格隔开的整数，为该树的前序遍历。Sample Input5 7 1 2 10Sample Output1453 1 24 5题型:树型动规用递归遍历整棵树。因为给出的是中序遍历,要求求出前序，所以实际上是区间动规。在读入数据时把ansii初始化为i的分数，表示当一棵子树中只有一个节点时的加分。把ansi-l i

3、初始化为i与il分数之和,root ilZ liZ为iT (这点很重要!因为有多解，所以只有这样才能和标准输出一样)。枚举每一个节点k作为根节点，递归查找f(I, k-l)*f(k+l, j)+scorek,保存最大值为 max 和 ko 结束循环时,ansi j=max, rooti j=k;最后递归输出即可。代码：(变量名稍有不同)#include<iostream>using namespace std;long ans4040, root4040, map40 = 0, n;long dfs (long x,long y)long s, sa, sb, anO, w;for

4、(s=x;s<=y;s+)if (x二sT && s+l<=y) if (ans x sT >=0) sa=ans x sT;else sa二dfs (x, sT);if(anss+1y>=0)sb二anss+1y;else sb二dfs (s+1, y);if(sa*sb+maps>an)an=sa*sb+maps;w二 s;ansxy=an;root x y二w;return an;void out(long x,long y)if(rootxy!=0)cout<<rootxy<<J;if (x!=y)out (x, root x y T);out (root x y+l, y);int main()long s;cin>>n; memset(ans, -1, sizeof(ans); for(s=l;s<=n;s+) cin>>maps;ansss=maps;rootss=s;ans sl s =maps +maps