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

.,树状动规,.,1333:VIJOS-P1180选课,想要选修某个课程，那么它的先修课必须要被选择。多叉树转二叉树动归。首先大家先了解多叉树转二叉树。原则：二叉树的结点x的左儿子为x的儿子，右儿子是x的兄弟。即左儿子，右兄弟原则。,.,1333:选课（多叉树转二叉树）,具体实现方法：使用数组模拟二叉树Lx:表示X的左儿子是谁!初值-1Rx:表示X的右儿子是谁！也就是X的兄弟，初值-1lastx:表示原树中x的当前一个子节点son1现在的位置，假如x的另外一个儿子son2,要插入到二叉树中那么根据左儿子右兄弟的原则，既然son2跟son1为兄弟，那么就放到son1所在位置的右子树即可！,代码：voidbuild(intx,inty)/y的父亲结点为xif(Lx=-1)Lx=y;elseRlastx=y;lastx=y;,.,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,.yF(Lx,k-1)+ax:表示左孩子选了k-1门课及包括课程x,共k门课的最大学分。F(Rx,y-k)表示右孩子只能选y-k门课的最大得分。分析出来了这么多，代码如何写才是关键，否则都是空中楼阁。我们引入记忆化搜索的思想，即每深搜一步，把搜做到的结果保存起来，当下次搜索到同样的位置时，直接使用！记忆化搜索经典题目：1911滑雪/递归退出条件if(fposk!=-1)returnfposk;/如果这个值以前被计算过，直接返回这个值fposk=work(rpos,k);/左子树不选任何一个for(inti=0;i=k-1;i+)fposk=max(fposk,work(lpos,i)+work(rpos,k-i-1)+spos);/动规过程returnfposk;,.,2140:通向自由的钥匙,通向自由的钥匙被放n个房间里，这n个房间由n-1条走廊连接。注意：这就是一棵树。本题的动规的过程与上一题选课是一样的唯一不同的是题目给出树的根为1，还有树的联通性。建二叉树树的过程是需要大家仔细思考的。,.,2140:通向自由的钥匙,voidbuild(intx)for(inti=1;i=n;i+)if(dxi)dxi=dix=0;if(lsx=-1)lsx=i;elserslastx=i;lastx=i;build(i);,.,1273:加分二叉树,每一个结点有一个权值，给定的序列是中序遍历的点权序列。状态fij表示从i到j的中序序列组成的二叉树最大加分值。方程fij=maxfik-1*fk+1j+fkki=ky)returnfxy=1;if(fxy!=-1)returnfxy;for(intk=0;kA再算一步。状态f0ij表示从i点走j步再回到i的最大值状态f1ij表示从i点走j步不回到i的最大值f0xj+2=maxf0xj+2,f0yk+f0xj-kf1xj+2=maxf1xj+2,f0yk+f1xj-kf1xj+1=maxf1xj+1,f1yk+f0xj-k,.,POJ2486AppleTree,voiddfs(intx)vx=1;for(inti=0;i=0;j-)for(intk=0;k=j;k+)f0xj+2=max(f0xj+2,f0yk+f0xj-k);f1xj+2=max(f1xj+2,f0yk+f1xj-k);f1xj+1=max(f1xj+1,f1yk+f0xj-k);,.,POJ3659CellPhoneNetwork,题意：给出一棵树，树的每个节点都可以放信号塔，放信号塔的节点可以覆盖到它周围的节点，问选择最少的建信号塔的方案，使得树的所有节点都被覆盖。这样的问题叫做：最小支配集问题，使用树形动归来处理。考虑每个结点只有两种状态，放或者不放信号塔。其中如果这个点不放信号塔，并且还需要被覆盖，又有两种情况：一是其父亲结点放信号塔，二是其子节点中有一个放了信号塔。总结起来每个结点有三种情况：fx0:x点的父亲结点放塔，以x为根的子树最少信号塔数fx1:x点的子节点放塔，以x为根的子树的最少信号塔数fx2:x点本身放信号塔，以x为根的子树最少信号塔数,.,POJ3659CellPhoneNetwork,那么动态方程为：设y为x的子结点fx0+=minfy1,fy2fx2+=minfy0,fy2fx1的情况比较复杂，需要单独讨论了。x的子节点y中是否存在y的自己覆盖小于y的子节点z的覆盖，如果存在(fy2fy1),那么这个y的分支就一定会被选中，进而辐射到y的根节点x。此时fx1=fx0;如果上述情况没有出现的话，只能选择一个最优的y，使得y点放信号塔，来辐射到x。令temp=fy2-fy1;那么fx1=fx0+temp;至此，动态转移方程就已经写完了，虽然有些复杂，但是对于我们深入理解动态规划有很深的影响。,.,POJ3659CellPhoneNetwork,结点的初值：fx0=0;fx1=0;fx2=1;如果是叶子结点呢？if（叶子）fx1=1=1;i-)x=de