树型动态规划

树型动态规划•朱全民•[e-mail]加分二叉树•设一个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个用空格隔开的整数，为该树的前序遍历。【输入样例】5571210【输出样例】14531245分析如果整棵树的权值最大，必然有左子树的权值最大，右子树德权值也最大，符合最优性原理。可行算法•我们试着写出状态转移方程：f[i,j]=max{i=t=j|d[t]+f[i,t-1]f[t+1,j]}初始：f(i,i)=d[i]目标：f(1,n)•这样，我们可以写出一个动态规划的算法，可以按照状态f[i,j]中i与j的距离来划分阶段(当然也有其它的划分阶段的办法),先处理掉边界情况(空树和只含有一个节点的树),然后就可以按照阶段自底向上进行动态规划了，最后再递归地输出，注意要保存每次决策。•时间复杂度O(n3)例二选课•大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。•每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，《数据结构》必须在选修了《高级语言程序设计》之后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为1，2，3，……。选课•下面举例说明•上例中1是2的先修课，即如果要选修2，则1必定已被选过。同样，如果要选修3，那么1和2都一定已被选修过。•学生不可能学完大学所开设的所有课程，因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。选课•输入输入文件的第一行包括两个正整数M、N（中间用一个空格隔开）其中M表示待选课程总数（1≤M≤1000)，N表示学生可以选的课程总数（1≤N≤M)。以下M行每行代表一门课，课号依次为1，2……M。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。•输出输出文件第一行只有一个数，即实际所选课程的学分总数。以下N行每行有一个数，表示学生所选课程的课号。样例分析7422010421717622表12157346图202157346图1分析•们可以选取某一个点k的条件只是它的父节点已经被选取或者它自己为根节点；而且我们不论如(何取k的子孙节点，都不会影响到它父节点的选取情况，这满足无后效性原则。于是我们猜测，是不是可以以节点为阶段，进行动态规划呢？•我们用函数f(i,j)表示以第i个节点为父节点，取j个子节点的最佳代价，则：•可是如此规划，其效率与搜索毫无差别，虽然我们可以再次用动态规划来使它的复杂度变为平方级，但显得过于麻烦。jnchnchjnchnchnchjnchnichnchnchjchinchinchifnchchfnchchfjif111122113)1(21)),()2,2()1,1((max),(改造树•转变为二叉树。如果两节点a,b同为兄弟，则将b设为a的右节点；如果节点b是节点a的儿子，则将节点b设为节点a的左节点。树改造完成后如图3。•我们用函数f(I,j)表示以第i个节点为父节点，取j个子节点的最佳代价，这和前一个函数表示的意义是一致的，但方程有了很大的改变：023014765图3转化为二叉树求解•1=i=m,1=j=n,0=kj•这个方程的时间复杂度最大为n3，十分优秀了。•在具体实现这道题时，我们可以自顶而下，用递归进行树的遍历求解}max{),(][)1,(),(),(iskjrightcfkleftcfjrightcfjif例三河流(IOI2005)•一颗有N+1个结点的树，树中的每个结点可能会生产出一些产品。这些产品要么就地加工（要有加工厂才行），要么运送到它的父亲结点那儿去。现在在整棵树的根结点处已经有了一个产品加工厂，而且所有的产品最终必须在某个加工厂加工才行。由于运费昂贵，不可能将所有的产品都运送到根节点处加工。现在决定在树中的某些结点新增总共K个加工厂，现在要你选择这K个加工厂的厂址。•假设结点i会生产出Wi吨产品，它的父结点是Pi。而它到它的父结点的路径的长度是Ui。运费的计算是每运送1顿的货物，每单位长度收取1的费用。根节点的编号为0。例三河流(IOI2005)•例如右图，0节点是根节点，如果要新增两个工厂，最佳方案是建在2、3两个节点上，这样总的费用为：•1*1（1号）+1*3（4号）=4•由于题目中给出的树是多叉树，不便于进行动态规划。我们先利用儿子兄弟表示法，将多叉树转化为二叉树。•进行了相关的转化之后，设f(i,j,k)表示在新树中，以i结点为根的子树中，分配k个加工厂。并且离i结点最近的加工厂在j结点的情况下。i结点及其子树内的所有产品，加工所需要的费用。•转移方程很容易就可以写出来：•总时间复杂度为O(N2K2)。例三河流(IOI2005)处设厂处不设厂ikkjrightsonifkileftsonifijiDisiwkkjrightsonifkjleftsonifkjif)1',,.()',,.(),()()',,.()',,.(),,(