NOI导刊树型动态规划

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,树型动态规划,长沙市雅礼中学 朱全民,加分二叉树,给定一个中序遍历为,1,2,3,n,的二叉树,每个结点有一个权值,定义二叉树的加分规则为：,左子树的加分,右子树的加分根的分数,若某个树缺少左子树或右子树，规定缺少的子树加分为,1,。,构造符合条件的二叉树,该树加分最大,输出其前序遍历序列,样例,中序遍历为,1,2,3,4,5,的二叉树有很多，下图是其中的三棵，其中第三棵加分最大，为,145.,分析,性质：中序遍历是按“左,-,根,-,右”方式进行遍历二叉树，因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边！,因此，假设二叉树的根结点为,k,，那么中序遍历为,1,2,n,的遍历序列，左孩子序列为,1,2,k-1,，右孩子序列为,k+1,k+2,n,，如下图,动态规划,设,f(i,j),中序遍历为,i,i+1,j,的二叉树的最大加分，则有：,f(i,j)=maxfi,k-1*fk+1,j+dk,显然,f(i,i)=di,答案为,f(1,n),1=i=k=j=n,时间复杂度,O(n,3,),要构造这个树，只需记录每次的决策值，令,b(i,j)=k,，表示中序遍历为,i,i+1,j,的二叉树的取最优决策时的根结点为,k,最后前序遍历这个树即可。,选课,给定,M,门课程，每门课程有一个学分,要从,M,门课程中选择,N,门课程，使得学分总和最大,其中选择课程必须满足以下条件：,每门课程最多只有一门直接先修课,要选择某门课程，必须先选修它的先修课,M,N=500,分析,每门课程最多只有,1,门直接先修课，如果我们把课程看成结点，也就是说每个结点最多只一个前驱结点。,如果把前驱结点看成父结点，换句话说，每个结点只有一个父结点。显然具有这种结构的模型是树结构，要么是一棵树，要么是一个森林。,这样，问题就转化为在一个,M,个结点的森林中选取,N,个结点，使得所选结点的权值之和最大。同时满足每次选取时，若选儿子结点，必选根结点的条件。,样例分析,如图,1,，为两棵树，我们可以虚拟一个结点，将这些树连接起来，那么森林就转会为了,1,棵树，选取结点时，从每个儿子出发进行选取。显然选,M=4,时，选,3,，,2,，,7,，,6,几门课程最优。,转化为二叉树,如果该问题仅仅只是一棵二叉树，我们对儿子的分配就仅仅只需考虑左右孩子即可，问题就变得很简单了。因此我们试着将该问题转化为二叉树求解。,图,2,就是对图,1,采用孩子兄弟表示法所得到的二叉树,动态规划,仔细理解左右孩子的意义（如右图）：,左孩子：原根结点的孩子,右孩子：原根结点的兄弟,也就是说，左孩子分配选课资源时，,根结点必须要选修，而与右孩子无关。,因此，我们设,f(i,j),表示以,i,为根结点的二叉树分配,j,门课程的所获得的最大学分，则有，,0=kj n m;,scoren+1=0;,brothern+1=0;,/,输入数据并转化为左儿子右兄弟表示法,for(int i=1;i a b;,if(a=0)a=n+1;,scorei=b;,brotheri=childa;,childa=i;,void dfs(int i,int j),if(visitedij)return;,visitedij=1;,if(i=0|j=0)return;,dfs(brotheri,j);/,如果不选,i,，则转移到状态,(brotheri,j),fij=fbrotherij;,for(int k=0;k fij),fij=fbrotherik+fchildij-k-1+scorei;,软件安装,（,2010,河南省选）,有,N,个软件，对于一个软件,i,，它要占用,W,i,的磁盘空间，它的价值为,V,i,。我们希望从中选择一些软件安装到一台磁盘容量为,M,计算机上，使得这些软件的价值尽可能大（即,V,i,的和最大）。,软件之间存在依赖关系，即软件,i,只有在安装了软件,j,（包括软件,j,的直接或间接依赖）的情况下才能正确工作（软件,i,依赖软件,j),。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为,0,。,我们现在知道了软件之间的依赖关系：软件,i,依赖软件,D,i,。一个软件只能被安装一次，如果一个软件没有依赖则,D,i,=0,，这时只要这个软件安装了，它就能正常工作。,现在请你设计出一种方案，安装价值尽量大的软件。,分析,由于软件存在先后约束关系，因此简单按软件先后顺序进行动态规划，会不符合无后效应原理，因此我们需要在进行动态规划前进行预处理。,若安装软件,i,必须先安装,j,则从,i,向,j,连一条有向弧，则软件的约束关系就构成了一个有向图。如下图：,可以看出如果有,k,个制约关系，则有,k,条边，中间会存在环,分析,处理环：,由于环为互为前提，要选择环中的一个必须都进行选择，因此可以将环缩成一个点，这个点为权值和价值为其他点的和。,孤立点没有与其他点也没有任何关系，可以不管。,如果把每个连通分量看成一棵树，则图变成了为一个森林，图,2,。,树型动态规划,显然这个森林可以采用树型动态规划，先将它儿叉树。,设,f(i,j),表示以,i,为根结点的二叉树分配,j,资源的最大价值,警卫安排,一个有,N,个区域的树结构上需要安排若干个警卫；,每个区域安排警卫所需要的费用是不同的；,每个区域的警卫都可以望见其相邻的区域，只要一个区域被一个警卫望见或者是安排有警卫，这个区域就是安全的；,任务：在确保所有区域都是安全的情况下，找到安排警卫的最小费用；,0n=720,；,分析样例,该图有,6,个区域如图,1,，安排情况如图,2,，红色点为安排了警卫。,2,号警卫可以观察,1,，,2,，,5,，,6,；,3,号警卫可以观察,1,，,3,；,4,号警卫可以观察,1,，,4,；,费用：,16+5+4=25,分析,对于每个点,i,，都有,3,种状态分别为：,要么在父亲结点安排警卫，即被父亲看到,要么在儿子结点安排警卫，即被儿子看到,要么安排警卫,对于,i,i,被父亲看到，这时,i,没有安排警卫，,i,的儿子要么安排警卫，要么被它的后代看到。,i,被儿子看到，即,i,的某个儿子安排了警卫，其他儿子需要安排警卫或者被它的后代看到。,i,安排了警卫，,i,的儿子可能还需要安排警卫，这样可能有更便易的方式照顾到它的后代；所以,i,的儿子结点被,i,看到，可能安排警卫，可能被它的后代看到。,动态规划,设,f(i,0),表示,i,结点被父亲看到；,f(i,1),表示,i,被它的儿子看到；,f(i,2),表示在,i,安排警卫；,则状态转移方程为：,时间复杂度,O(N,2,),procedure work(now:longint);,var i,j,sum,tmp:longint;,begin,for i:=1 to tnow do work(wnow,i);,/,对每个儿子进行处理,fnow,0:=0;/,以下处理,now,被父亲看到,for i:=1 to tnow do inc(fnow,0,fwnow,i,1);/now,的儿子被儿子看到,sum:=0;,/,以下处理在,now,被儿子看到的,for i:=1 to tnow do /now,的儿子被儿子看到或者或安排警卫；,inc(sum,min(fwnow,i,1,fwnow,i,2);,fnow,1:=maxlongint;,for i:=1 to tnow do,/,枚举哪个儿子放警卫,begin,tmp:=sum-min(fwnow,i,1,fwnow,i,2)+fwnow,i,2;,fnow,1:=min(fnow,1,tmp);,end;,fnow,2:=cnow;/,以下处理在,now,放置警卫,for i:=1 to tnow do Inc(fnow,2,min(min(fwnow,i,0,fwnow,i,1),fwnow,i,2);,fnow,1:=min(fnow,1,fnow,2);1,包含了,2,状态，取优值,end;,总结,树型动态规划有一个共性，那就是它的基本模型都是一棵树或者森林，为了考虑方便，一般情况下都将这个树或森林转化为二叉树，如下图，然后整个问题的最优只会涉及到左右孩子的最优，然后考虑根结点的情况，这样化简了问题，最终很容易写出状态转移方程，从而问题得到解决。,另外，并不是所有的问题一定要转化为二叉树来解决，要仔细思考的就是每个结点有些什么状态，这些结点的状态与父、子结点的状态有什么联系，也就是如何由子结点的最优值推出父节点的最优值,(,即状态转移方程,),。,