浅谈树的动态规划

《浅谈树的动态规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅谈树的动态规划树，是一种很特殊的数据结构，关于它的题目十分的多，儿乎在大部分的比赛当中都会出现这类型的题冃，而口研究树的题冃也是十分有趣的。由于以树为背景，题H会很明显地渗透了树的特征，而树的特征也正是我们解决这类问题的突破UO树的问题往往会有一个十分突出的特点：数据量十分大。由于树是十分特殊的图：连通图，n个顶点，ml条边。因此在空间町以承受的范围内n可以达到很大。而且树的特殊结构也决定了算法的优越性。正因为树的特殊，通常能够找到十分高效的算法(比如说是0(n))。于是我们解决这类题目的时候应

2、当牢牢抓住树的特征，认真分析问题，这样就能比较好地解决题目了。下面举一些例子谈谈树的动态规划。树的动态规划，顾名思义，就是在树上面进行动态规划。树的动态规划很有特点，虽说对某个结点來说，状态转移的复杂度是不确定的(这取决于与它相连的边数)，但是总体來说，每条边通常只会对应常数次状态转移，所以总的复杂度是0(n)的，这就使树的动态规划十分高效。例如下面这道题目：『例1』ComputerNetworkAschoolboughtthefirstcomputersometimeago.Duringther

3、ecentyearstheschoolboughtN~1newcomputers.Eachnewcomputerwasconnectedtooneofsettledearlier.Managersofschoolareanxiousabouts1owfunctioningofthenetandwanttoknowforeachcomputernumberSi-maximumdistance,forwhichi-thcomputerneedstosendsignal(i.e.lengthofcabl

4、etothemostdistantcomputer).Youneedtoprovidethisinformalion.InputThereisnaturalnumberN(N<=10000)inthefirstlineofinput,foilowedby(N~l)lineswithdescriptionsofcomputers・i-thlinecontainstwonaturalnumbers-numberofcomputer,towhichi~thcomputerisconnecledandle

5、ngthofcableusedforconneelion.Totallengthofcabledoesnotexceed109.Numbersinlinesofinputareseparatedbyaspace・OutputWriteNlinesinoutputfile.i-thlinemustcontainnumberSifori-thcomputer(l<=i<=N).Sampletest(s)Input31112Output233题目的意思是说：一间学校前几年时间买进了第一台电脑。这几年又陆

6、续买TN-1台电脑。后面买的电脑都与先前买的某一台电脑用网线连接起来。现在我们知道后面的N-1台电脑分别与哪台电脑连接以及相应的网线的长度，任务是对每一台电脑K都求出，在另外的N-1台电脑中，离K最远的那台电脑与K的距离（即它们Z间的网线的总长度）。这也是一道关于树的题目，而月•和例1十分相似，也是符合动态规划的耍求的。我们也可以类似地先任意选择一个结点作为树的根把树转为有根树，然后用动态规划对每个结点K都求出以结点K为根的子树的深度。然而我们同样碰到了上面的问题，就是K的父亲A也会连出去一棵树，

7、它在原来的无根树中同样也属于K的了树（即K的“上方了树”）。但是，现在我们要求的是树的深度，就不像上题求结点数那样这么容易求了。如呆我们仍然用动态规划，从A的子树（除去K这一棵）中选出深度最深的，然后将它的深度加上AK的长作为“上方子树”的深度，就有可能出现下面这种情况：对于A的每一个儿子K,都要求K的“上方子树”，而每一次我们都必须求A的所有子树（除去K的那一•棵）中深度最大的那一棵。这样的话时间复朵度就变为0（n2）了，显然是十分不优的。为了解决这个问题，我们在前面那个过程中，求A的所有子树的

8、深度的时候，可以顺便求出A的了树中深度最大的两棵，并记录是哪两棵。在以后求K的“上方子树”时，就能判断一下，K是不是它父亲A的最深的子树。如果不是，那么A的最深的子树的深度加上AK的长度就是K的“上方子树”的深度；否则A的第二深的子树的深度加上AK的长度就是K的“上方子树”的深度。这样就能够用0（n）的复杂度求岀所有结点的“上方子树”的深度了。解决了这些问题后我们就能直接进行输出了。（程序请参见附录）在2003年的全国赛中也冇一道十分类似的题目：『例2』数据生成器【题目背景】小明在