树形动态规划(信息学竞赛)课件

1、树状动规,1,PPT学习交流,1333: VIJOS-P1180 选课,想要选修某个课程，那么它的先修课必须要被选择。 多叉树转二叉树动归。 首先大家先了解多叉树转二叉树。 原则：二叉树的结点x的左儿子为x的儿子，右儿子是x的兄弟。即左儿子，右兄弟原则。,2,PPT学习交流,1333: 选课 （多叉树转二叉树）,具体实现方法：使用数组模拟二叉树 Lx:表示X的左儿子是谁!初值-1 Rx:表示X的右儿子是谁！也就是X的兄弟，初值-1 lastx:表示原树中x的当前一个子节点son1现在的位置，假如x的另外一个儿子son2,要插入到二叉树中那么根据左儿子右兄弟的原则，既然son2跟son1为兄弟，

2、那么就放到son1所在位置的右子树即可！,代码： void build(int x,int y) /y的父亲结点为x if(Lx=-1) Lx = y; else R lastx = y; lastx=y; ,3,PPT学习交流,1333: VIJOS-P1180 选课,状态F(x,y)：表示节点x取y门课得最高学分 方程F(x,y)=maxF(Rx,k) , F(Lx,k-1) + ax + F(Rx,y-k) k=0,1,.y F(Lx,k-1)+ax :表示左孩子选了k-1门课及包括课程x,共k门课的最大学分。 F(Rx,y-k) 表示右孩子只能选y-k门课的最大得分。 分析出来了这么多

3、，代码如何写才是关键，否则都是空中楼阁。 我们引入记忆化搜索的思想，即每深搜一步，把搜做到的结果保存起来，当下次搜索到同样的位置时，直接使用！ 记忆化搜索经典题目：1911滑雪 /递归退出条件 if(fposk != -1) return fposk; /如果这个值以前被计算过，直接返回这个值 fposk=work(rpos,k); /左子树不选任何一个 for(int i=0;i=k-1;i+) fposk=max(fposk , work(lpos,i)+work(rpos,k-i-1)+spos ); /动规过程 return fposk; ,5,PPT学习交流,2140: 通向自由的钥

4、匙,通向自由的钥匙被放n个房间里，这n个房间由n-1条走廊连接。注意：这就是一棵树。 本题的动规的过程与上一题选课是一样的 唯一不同的是题目给出树的根为1，还有树的联通性。 建二叉树树的过程是需要大家仔细思考的。,6,PPT学习交流,2140: 通向自由的钥匙,void build(int x) for(int i=1;i=n;i+) if(dxi) dxi=dix=0; if( lsx=-1 ) lsx=i; else rs lastx =i; lastx=i; build(i); ,7,PPT学习交流,1273: 加分二叉树,每一个结点有一个权值，给定的序列是中序遍历的点权序列。 状态fi

5、j表示从i到j的中序序列组成的二叉树最大加分值。 方程fij=max fik-1 * fk+1j + fkk i=k=j fik-1 和 fk+1j 直接拿过来用肯能不会求出最大的fij,所以要引入记忆化的思想，递归的求出这两个的值。,8,PPT学习交流,1273: 加分二叉树,long long work(int x,int y) if(xy) return fxy=1; if(fxy!=-1) return fxy; for(int k=0;k=y-x;k+) if(fxyfx+kx+k+work(x,x+k-1)*work(x+k+1,y) ) fxy=fx+kx+k+work(x,x+

6、k-1)*work(x+k+1,y); rootxy=x+k; /记录x到y区间的根，以便最后递归输出先根遍历。 return fxy; ,9,PPT学习交流,POJ 2342 Anniversary party,题意：一个人不同他的直属上司一起参加舞会，问参会人员的权值和的最大值。 显然每个人只有两种状态参加或者不参加 状态fi0表示第i个人不参加，fi1表示此人参加，所的得到的子树的最大值。 fi1+=fj0;j是其下属的标号 fi0+=max fj1,fj0 本题使用链式前向星存边，找出根root ans=max froot0, froot1;,10,PPT学习交流,POJ 2342 A

7、nniversary party,void work(int x) fx0=0 , fx1=ax; /初始化 for(int y,i=headx;i;i=nexti) y=toi;/y为x的子节点 work(y);/先处理完y才能动规x fx0+=max(fy0,fy1); fx1+=fy0; ,11,PPT学习交流,POJ 3342 Party at Hali-Bula,基本题意与2342相同，需要特别判断与会名单是否唯一！ 思考判定方法？是否有特例！ 动规伴随着深搜，只需要考虑深搜时候的局部情况即可判定全局情况。 即if(fx0=fx1 思考当n=2时，只能一个人与会，名单不确定。但是使用

8、上面的判断就不行了，需要特判一下即可。,12,PPT学习交流,POJ 2486 Apple Tree,N叉苹果树，结点上有苹果，问一共走k步，所能吃到的苹果的最大值。 其中从A-B 算一步，返回B-A再算一步。 状态f0ij表示从i点走j步再回到i的最大值 状态f1ij表示从i点走j步不回到i的最大值 f0 xj+2=maxf0 xj+2,f0yk+f0 xj-k f1xj+2=maxf1xj+2,f0yk+f1xj-k f1xj+1=maxf1xj+1,f1yk+f0 xj-k,13,PPT学习交流,POJ 2486 Apple Tree,void dfs(int x) vx=1; for(

9、int i=0;i=0;j-) for(int k=0;k=j;k+) f0 xj+2=max(f0 xj+2 , f0yk+f0 xj-k ); f1xj+2=max(f1xj+2 , f0yk+f1xj-k ); f1xj+1=max(f1xj+1 , f1yk+f0 xj-k ); ,14,PPT学习交流,POJ 3659 Cell Phone Network,题意：给出一棵树，树的每个节点都可以放信号塔，放信号塔的节点可以覆盖到它周围的节点，问选择最少的建信号塔的方案，使得树的所有节点都被覆盖。 这样的问题叫做：最小支配集问题，使用树形动归来处理。 考虑每个结点只有两种状态，放或者不放

10、信号塔。其中如果这个点不放信号塔，并且还需要被覆盖，又有两种情况：一是其父亲结点放信号塔，二是其子节点中有一个放了信号塔。 总结起来每个结点有三种情况： fx0:x点的父亲结点放塔，以x为根的子树最少信号塔数 fx1:x点的子节点放塔，以x为根的子树的最少信号塔数 fx2:x点本身放信号塔，以x为根的子树最少信号塔数,15,PPT学习交流,POJ 3659 Cell Phone Network,那么动态方程为：设y为x的子结点 fx0+=min fy1 , fy2 fx2+=min fy0 , fy2 fx1的情况比较复杂，需要单独讨论了。 x的子节点y中是否存在y的自己覆盖小于y的子节点z的

11、覆盖，如果存在(fy2fy1),那么这个y的分支就一定会被选中，进而辐射到y的根节点x。此时fx1=fx0; 如果上述情况没有出现的话，只能选择一个最优的y，使得y点放信号塔，来辐射到x。令temp=fy2-fy1;那么fx1=fx0+temp; 至此，动态转移方程就已经写完了，虽然有些复杂，但是对于我们深入理解动态规划有很深的影响。,16,PPT学习交流,POJ 3659 Cell Phone Network,结点的初值： fx0=0; fx1=0; fx2=1; 如果是叶子结点呢？ if（叶子） fx1=130; 最后的ans呢？ ans=min（ froot1 , froot2 ）,17

12、,PPT学习交流,poj 3398 Perfect Service,同样是最小支配集问题。 我们使用另类的贪心方法来解决。 1、深搜遍历，把深搜的顺序记录下来。其实深搜的顺序就是先根遍历的顺。 2、根据先跟遍历的顺序逆向处理，也就是相当于回溯的过程。 3、如果一个结点x的覆盖状态markx=0,并且如果其根fax的是否为server的状态为0，即setfax=0,那么ans+，setfax=1; 4、不管setfax是否为0，都要标记x,fax,fafax的状态为覆盖。思考为什么？,18,PPT学习交流,poj 3398 Perfect Service,void dfs(int x) deep+num=x; for(int y,i=headx;i;i=nexti) y=toi; if(!vy) vy=1;fy=x; dfs(y