试题(树型动规)
1.加分二叉树(binary.c/cpp) NOIP2003提高组第3题
【问题描述】
设一个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
3 1 2
4 5
F(I,j) I,i+1…..j
枚举K（根结点）
F(I,j)=max{d[k]+f[I,K-1]*f[K+1,j]}
1…I K…..j…..n
F(I,i)=d[k]
F(1,n)\
边界：空树和只含有一个结点的树
自底向上递归前序遍历（根－左－右）二维数组记录决策
时间复杂度：I j K N3 30*30*30=27000
最高加分：4*109 int 2.1*109long float double(双精度)
2.二叉苹果树（apple.c/cpp）URAL 1018
【问题描述】
有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树：
2 5
\ /
3 4
\ /
1
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
【输入格式】
第1行2个数，N和Q(1<=Q<= N,1 N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。 每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。 每根树枝上的苹果不超过30000个。 【输出格式】 一个数，最多能留住的苹果的数量。 【输入样例】 5 2 1 3 1 1 4 10 2 3 20 3 5 20 【输出样例】 21 3.选课(curricula.c/cpp) CTSC 97 【问题描述】 大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。 每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，《数据结构》必须在选修了《高级语言程序设计》之后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为1，2，3，……。下面举例说明 课号先修课号学分 1 无 1 2 1 1 3 2 3 4 无 3 5 2 4 上例中1是2的先修课，即如果要选修2，则1必定已被选过。同样，如果要选修3，那么1和2都一定已被选修过。 学生不可能学完大学所开设的所有课程，因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。 【输入格式】 输入文件的第一行包括两个正整数M、N（中间用一个空格隔开）其中M表示待选课程总数（1≤M≤1000)，N表示学生可以选的课程总数（1≤N≤M)。 以下M行每行代表一门课，课号依次为1，2……M。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。 【输出格式】 输出文件第一行只有一个数，即实际所选课程的学分总数。以下N行每行有一个数，表示学生所选课程的课号。 【输入样例】 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2 【输出样例】 13 2 6 7 3 4.小胖守皇宫(guard.c/cpp) VIJOS 【问题描述】 huyichen世子事件后，xuzhenyi成了皇上特聘的御前一品侍卫。 皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；有边相连的宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。 可是xuzhenyi手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。 帮助xuzhenyi布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。 【输入格式】 输入文件中数据表示一棵树，描述如下： 第1行n，表示树中结点的数目。 第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0 对于一个n（0 < n <= 1500）个结点的树，结点标号在1到n之间，且标号不重复。【输出格式】 输出文件仅包含一个数，为所求的最少的经费。 【样例输入】 6 1 30 3 2 3 4 2 16 2 5 6 3 5 0 4 4 0 5 11 0 6 5 0 【样例输出】 25 5.贪吃的九头龙（dragon.c/cpp ）NOI2002 【问题描述】 传说中的九头龙是一种特别贪吃的动物。虽然名字叫“九头龙”，但这只是说它出生的时候有九个头，而在成长的过程中，它有时会长出很多的新头，头的总数会远大于九，当然也会有旧头因衰老而自己脱落。 有一天，有M 个脑袋的九头龙看到一棵长有N 个果子的果树，喜出望外，恨不得一口把它全部吃掉。可是必须照顾到每个头，因此它需要把N 个果子分成M 组，每组至少有一个果子，让每个头吃一组。 这M 个脑袋中有一个最大，称为“大头”，是众头之首，它要吃掉恰好K 个果子，而且K 个果子中理所当然地应该包括唯一的一个最大的果子。果子由N-1根树枝连接起来，由于果树是一个整体，因此可以从任意一个果子出发沿着树枝“走到”任何一个其他的果子。 对于每段树枝，如果它所连接的两个果子需要由不同的头来吃掉，那么两个头会共同把树枝弄断而把果子分开；如果这两个果子是由同一个头来吃掉，那么这个头会懒得把它弄断而直接把果子连同树枝一起吃掉。当然，吃树枝并不是很舒服的，因此每段树枝都有一个吃下去的“难受值”，而九头龙的难受值就是所有头吃掉的树枝的“难受值”之和。 九头龙希望它的“难受值”尽量小，你能帮它算算吗？ 例如图1所示的例子中，果树包含8个果子，7段树枝，各段树枝的“难受值”标记在了树枝的旁边。九头龙有两个脑袋，大头需要吃掉4个果子，其中必须包含最大的果子。即N=8，M=2， K=4： 图一描述了果树的形态，图二描述了最优策略。 【输入格式】 输入文件dragon.in 的第1行包含三个整数N (1<=N<=300)，M (2<=M<=N)，K (1<=K<=N)。 N 个果子依次编号1,2,...,N ，且最大的果子的编号总是1。第2行到第N 行描述了果树的形态，每行包含三个整数a (1<=a<=N)，b (1<=b<=N)，c (0<=c<=105)，表示存在一段难受值为c 的树枝连接果子a 和果子b 。 【输出格式】 输出文件dragon.out 仅有一行，包含一个整数，表示在满足“大头”的要求的前提下，九头龙的难受值的最小值。如果无法满足要求，输出-1。 【样例输入】 8 2 4 1 2 20 1 3 4 1 4 13 2 5 10 2 6 12 3 7 15 3 8 5 【样例输出】 4 大头吃4个果子，用实心点标识； 小头吃4个果子，用空心点标识； 九头龙的难受值为4，因为图中用细边标记的树枝被大头吃掉了。 图一 图二 最大的果子 5.二叉查找树（treapmod.c/cpp）NOI2009 【问题描述】 已知一棵特殊的二叉查找树。根据定义，该二叉查找树中每个结点的数据值都比它左子树结点的数据值大，而比它右子树结点的数据值小。 另一方面，这棵查找树中每个结点都有一个权值，每个结点的权值都比它的儿子结点的权值要小。 已知树中所有结点的数据值各不相同；所有结点的权值也各不相同。这时可得出这样一个有趣的结论：如果能够确定树中每个结点的数据值和权值，那么树的形态便可以唯一确定。因为这样的一棵树可以看成是按照权值从小到大顺序插入结点所得到的、按照数据值排序的二叉查找树。 一个结点在树中的深度定义为它到树根的距离加1。因此树的根结点的深度为1。 每个结点除了数据值和权值以外，还有一个访问频度。我们定义一个结点在树中的访问代价为它的访问频度乘以它在树中的深度。整棵树的访问代价定义为所有结点在树中的访问代价之和。 现在给定每个结点的数据值、权值和访问频度，你可以根据需要修改某些结点的权值，但每次修改你会付出K的额外修改代价。你可以把结点的权值改为任何实数，但是修改后所有结点的权值必须仍保持互不相同。现在你要解决的问题是，整棵树的访问代价与额外修改代价的和最小是多少？ 【输入格式】 输入文件名为treapmod.in。 输入文件第一行包含两个正整数N和K。N为结点的个数，K为每次修改所需的额外修改代价。 接下来一行包含N个非负整数，是每个结点的数据值。 再接下来一行包含N个非负整数，是每个结点的权值。 再接下来一行包含N个非负整数，是每个结点的访问频度。 所有的数据值、权值、访问频度均不超过400000。每两个数之间都有一个空格分隔，且行尾没有空格。 【输出格式】 输出文件名为treapmod.out。输出文件只有一个数字，即你所能得到的整棵树的访问代价与额外修改代价之和的最小值。 【输入样例】 4 10 1 2 3 4 1 2 3 4 1 2 3 4 【输出样例】 29 【样例说明】 输入的原图是左图，它的访问代价是1×1+2×2+3×3+4×4=30。最佳的修改方案是把输入中的第3个结点的权值改成0，得到右图，访问代价是1×2+2×3+3×1+4×2=19，加上额外修改代价10，一共是29。 【数据规模】 40%的数据满足N ≤ 30; 70%的数据满足N ≤ 50; 100%的数据满足N ≤ 70, 1 ≤ K ≤ 30000000。 数据值：1 权值：1 数据值：2 权值：2 数据值：3 权值：3 数据值：4 权值：4 数据值：1 权值：1 数据值：2 权值：2 数据值：3 权值：0 数据值：4 权值：4 6．河流（river.c/cpp）IOI2005 【问题描述】 几乎整个Byteland 王国都被森林和河流所覆盖。小点的河汇聚到一起，形成了稍大点的河。就这样，所有的河水都汇聚并流进了一条大河，最后这条大河流进了大海。这条大河的入海口处有一个村庄——名叫Bytetown. 在 Byteland 国，有n 个伐木的村庄，这些村庄都座落在河边。目前在 Bytetown，有一个巨大的伐木场，它处理着全国砍下的所有木料。木料被砍下后，顺着河流而被运到Bytetown 的伐木场。Byteland 的国王决定，为了减少运输木料的费用，再额外地建造 k 个伐木场。这 k 个伐木场将被建在其他村庄里。这些伐木场建造后，木料就不用都被送到Bytetown 了，它们可以在运输过程中第一个碰到的新伐木场被处理。显然，如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。 注：所有的河流都不会分叉，形成一棵树，根结点是 bytetown。 国王的大臣计算出了每个村子每年要产多少木料，你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为：每一吨木料每千米 / 1分钱。 编一个程序： 1．从文件读入村子的个数，另外要建设的伐木场的数目，每年每个村子产的木料的块数以及河流的描述。 2．计算最小的运费并输出。 【输入格式】 第一行包括两个数 n（2<=n<=100），k（1<=k<=50,且 k<=n）。n 为村庄数，k 为要建的伐木场的数目。除了bytetown 外，每个村子依次被命名为 1，2，3……n，Bytetown被命名为 0。 接下来 n 行，每行3 个整数 wi——每年 i 村子产的木料的块数（0<=wi<=10000） vi——离 i 村子下游最近的村子（即 i 村子的父结点）（0<=vi<=n） di——vi 到 i 的距离(千米)。（1<=di<=10000） 保证每年所有的木料流到bytetown 的运费不超过2000,000,000 分 50％的数据中 n 不超过 20。 【输出格式】 输出最小花费，精确到分。 【样例输入】 4 2 1 0 1 1 1 10 10 2 5 1 2 3 【样例输出】 4