1、陈益波陈益波香港城市大学香港城市大学20112011年年7 7月月3030日日华中科大华中科大2011 ACM2011 ACM暑期集训暑期集训动态规划（三）动态规划（三）状态压缩状态压缩DP DP 及及 树型树型DPDP个人简介祖籍：浙江香港城市大学 商学院 09级PhD管理科学专业 Operation Research.QQ: 112997821人人网: 陈益波Email: 主要内容状态压缩思想状态压缩DP例题讲解树型DP特征树型DP例题讲解总结内容来源树型动态规划和状态压缩动态规划 -wangfangbob动态规划的状态方程树形动态规划，状态压缩，结果与参数的互换 -李子星树型动态规划的实
2、例分析 -李彦亭什么是树型动态规划顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：根叶：不过这种动态规划在实际的问题中运用的不多，也没有比较明显的例题，所以不在今天讨论的范围之内。叶根：既根的子节点传递有用的信息给根，完后根得出最优解的过程。这类的习题比较的多，下面就介绍一些这类题目和它们的一般解法。例题一：HDUHDU 2412 2412 PARTY AT HALI-BULA题目大意：n个人形成一个关系
3、树，每个节点代表一个人，节点的根表示这个人的唯一的直接上司，只有根没有上司。要求选取一部分人出来，使得每2个人之间不能有直接的上下级的关系，求最多能选多少个人出来，并且求出获得最大人数的选人方案是否唯一。这是一个经典的树型动态规划。状态？转移？1.2 PARTY AT HALI-BULA 简单的染色统计是不正确的1.3 PARTY AT HALI-BULA人之间的关系形成树型结构DP, 用dpi0表示不选择i点时，i点及其子树能选出的最多人数，dpi1表示选择i点时，i点及其子树的最多人数。1.4 PARTY AT HALI-BULA状态转移方程:对于叶子节点 dpk0 = 0, dpk1 =
4、 1对于非叶子节点i,dpi0 = max(dpj0, dpj1) (j是i的儿子)dpi1 = 1 + dpj0 (j是i的儿子) 最多人数即为max(dp00, dp01)如何判断最优解是否唯一?1.5 PARTY AT HALI-BULA新加一个状态dupij，表示相应的dpij是否是唯一方案。对于叶子结点, dupk0 = dupk1 = 1.对于非叶子结点,对于i的任一儿子j，若(dpj0 dpj1 且 dupj0 = 0) 或 (dpj0 dpj1 且 dupj1 = 0) 或 (dpj0 = dpj1)，则dupi0 = 0对于i的任一儿子j有dupj0 = 0, 则dupi1
5、= 0例题二：STRATEGIC GAME 题目大意：一城堡的所有的道路形成一个n个节点的树，如果在一个节点上放上一个士兵，那么和这个节点相连的边就会被看守住，问把所有边看守住最少需要放多少士兵。典型的树型动态规划状态？转移？2.2 STRATEGIC GAMEdproot i 表示以i为根的子树，在i上放置一个士兵，看守住整个子树需要多少士兵。all i 表示看守住整个以i为根的子树需要多少士兵。2.3 STRATEGIC GAME状态转移方程： 叶子节点：dprootk =1； allk = 0； 非叶子节点： dprooti = 1 + allj(j是i的儿子)； alli = min(
6、 dprooti, dprootj(j是i的儿子) );这个题目还是比较简单的，如果把题目中看守边变成看守相邻的点呢？留给你来思考_例题三例题三 加分二叉树加分二叉树 设一个n个节点的二叉树tree的中序遍历为（l,2,3,n），其中数字1,2,3,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分 subtree的右子树的加分subtree的根的分数 若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试
7、求一棵符合中序遍历为（1,2,3,n）且加分最高的二叉树tree。3.2 基础回顾树的中序遍历若二叉树为空则结束返回，否则：（1）中序遍历左子树。（2）访问根结点。（3）中序遍历右子树。树的前序遍历若二叉树为空则结束返回，否则：（1）访问根结点. .（2）前序遍历左子树. .（3）前序遍历右子树. .3.3 样例【输入格式】 第1行：一个整数n（n30），为节点个数。 第2行：n个用空格隔开的整数，为每个节点的分数（分数100）。【输出格式】 第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。 第2行：n个用空格隔开的整数，为该树的前序遍历。【输入样例】 5 5 7 1
8、2 10【输出样例】 145 3 1 2 4 53.4 分析本题适合用动态规划来解。如果用数组valuei,j表示从节点i到节点j所组成的二叉树的最大加分，则动态方程可以表示如下：valuei,j=maxvaluei,i+valuei+1,j, valuek,k+valuei,k*valuek+1,j | ikj, valuei,j-1 + valuej,j ;第一项 为 左子树为空， 根为i，右子树i+1,j。第二项 为 左子树为i,根为i+1,右子树为i+2,j.树型动态规划总结必要条件：子树之间不可以相互干扰，如果本来是相互干扰的，那么我们必须添加变量使得他们不相互干扰。树形动态规划通常
9、从叶节点（边界）开始逐步向上一层的节点（即父节点）进行状态方程的转移，直到根节点。内容二 状态压缩动态规划状态压缩动态规划： 用尽量少的状态表示出DP的整个过程。压缩所有不必要的信息。典型方式：当需要表示一个集合有哪些元素时，往往利用2进制用一个整数表示。例题四：经典问题TSP一个n个点的带权的有向图，求一条路径，使得这条路经过每个点恰好一次，并且路径上边的权值和最小（或者最大）。或者求一条具有这样性质的回路，这是经典的TSP问题。n = 16 (重要条件,状态压缩的标志)状态？转移？4.2 TSP如何表示一个点集：由于只有16个点，所以我们用一个整数表示一个点集：例如： 5 00000000
10、00000101；（2进制表示） 它的第0位和第2位是1，就表示这个点集里有2个点，分别是点0和点2。 31 0000000000011111； （2进制表示） 表示这个点集里有5个点，分别是0，1，2，4，5；4.3 TSP所以一个整数i就表示了一个点集；整数i可以表示一个点集，也可以表示是第i个点。状态表示：dpij表示经过点集i中的点恰好一次，不经过其它的点，并且以j点为终点的路径,权值和的最小值，如果这个状态不存在，就是无穷大。4.4 TSP状态转移： 单点集：状态存在dp1jj = 0；否则无穷大。非单点集： 状态存在 dpij = min(dpks + wsj) k表示i集合中去掉
11、了j点的集合，s遍历集合k中的点并且dpks状态存在， 点s到点j有边存在，wsj表示边的权值。 状态不存在 dpij为无穷大。4.5 TSP最后的结果是： min( dp( 1n ) 1j ) ( 0 = j n )；技巧：利用2进制，使得一个整数表示一个点集，这样集合的操作可以用位运算来实现。例如从集合i中去掉点j： k = i & ( ( 1 j ) ) 或者 k = i - ( 1 j )例题五：走道铺砖问题题意：给定一个n*m，(n,m=20)的走道（因为是走道，所以宽度很小，但长度可能很长，保证n*m为偶数），问用1*2的砖块铺满这个走道的方案数有多少。（不用考虑翻转旋转相同的问题
12、，即求的不是本质不同解的数目。）状态？转移？5.2 走道铺砖问题方法：用fi,j表示从第1行铺到第i行，前i-1行已经全部铺满，且第且第i i行没有横着放的砖行没有横着放的砖，且第i行的铺砖状态为j的二进制数对应的状态，的铺砖方案总数。 1 0 1 0 1 1第i行用fi,43表示蓝色部分已经确定了的所有铺砖方案数可以很容易得联想到用fi-1,0.2m-1推出fi,0.2m-1的思路：fi,j=sum fi-1, x | 0=x0 do begina=lowbit(x); x-=lowbit(x);If (x=0) return false;b=lowbit(x); x-=lowbit(x);
13、If (ba*2) return false;endreturn true5.3 走道铺砖问题0011011110中的所有1就可以用横着的砖盖满，而00111010就不行。判定可以利用lowbit，每轮取走两位lowbit，如果后取的不是先取的值的两倍，说明两次取的不是相邻的数位。5.4 走道铺砖问题最后的结果就是：sum fn, x | 0=x2m且db(2m-1-x) 计算的时间复杂度则是O(n*22m)。实际上把f的状态转移方程稍微变一下形式：fi,j=sum fi-1, 2m-1-x-j | 0=x2m且db(x)且x&j=0) 就可以发现，x完全不需要从0一直枚举到2m，只需要枚举有
14、限的若干项在0到2m范围内能通过db判定的x就可以了。5.5 走道铺砖问题最后的结果就是：sum fn, 2m-1-x | 0=x2m且db(x) 计算的时间复杂度则是O(n*y2)，其中y=count x | 0=x0的转移初始其它转移？*5.9 其它转移, K0,j的第k-1位为0 If(j的k-2位不为0） fikj = fik-1j(1(k-1) Else /j的k-2位也為0 fikj = fik-1j(10,j的第k-1位为1 Fikj = fik-1j (1(k-1);5.11 转移代码/ 初始化 dp0mj = 1，如果j可以摆得出，否则dp0mj=0;for(int i=1;
15、in;i+) for(int j=0;j(1m);j+) /k=0 dpi0j = dpi-1mj; for(int j=0;j(1m);j+) /k=1 dpi1j = dpi0j1; for(int k=2;k=m;k+) /k=2,3,.,m; for(int j=0;j(1m);j+) dpikj = dpik-1j(1(k-1); if( (j&(1(k-1) = 0 & (j&(1(k-2) = 0 ) dpikj += dpik-2j; 最终答案 为 dpn-1m0的值思考題：思考題：方格选数最大方格选数最大 HDUHDU21672167题目大意：Youre given an u
16、nlimited number of pebbles to distribute across an N x N game board (N drawn from 3, 15), where each square on the board contains some positive point value between 10 and 99, inclusive. 给定一个N*N个矩阵（3=N=15)，要你选择若干个数，使得最后所选的数总和最大。选数的规则是如果选了某个数，那么它的八个相邻方向的数都不能选。状态？转移？例题六：优盘质量题意：n个完全相同的优盘和h层高楼，希望知道优盘最高在哪
17、一层扔下来不会坏（定义为结实度），问最坏的情况下要扔几次。比如2个优盘4层楼，先从3楼扔，如果没坏，那么再在4楼扔如果坏了，那么还剩1个优盘，再在1楼扔如果坏了，那么就是1层如果没坏，那么再在2楼扔所以这个方案最坏要扔3次。而且一定不会用到第3个优盘。6.2 优盘质量比较容易想到的是用fi,j表示现在有i层楼，j个优盘，最好的方案最坏要扔多少次。状态转移方程可以这样考虑：假定第一次在第x层试。如果坏了的话，下一步就是要确定在第1到第x-1层哪一层会坏或者都不会坏，而这一步还剩下j-1个优盘，所以这一步最少要扔的次数就应该是fx-1,j-1。如果没坏的话，下一步就是要确定在第x+1到第i层哪一层
18、会坏或者都不会坏，而这一步还剩下j个优盘，所以这一步最少要扔的次数就应该是fi-x,j。6.3 优盘质量要考虑最坏的情况，所以第一次在第x层试的最坏要扔的次数就是maxfx-1,j-1,fi-x,j+1。所以fi,j=min max fx-1,j-1 , fi-x,j +1 | 1=x=h，最后的结果就是k。fi-1,jfi-1,j-1fi,j第一次扔的一层6.6 优盘质量首先，这个的状态转移的代价就比之前的要小。而且，深入考虑的话，可以发现：（一）如果fi,j已经大于等于h的最大值了的话，那么fi,j+1就不用再算下去了，并且如果i1=C(i,j)一定成立（fi,j的递推是不是像杨辉三角），
19、即当C(i,j)=maxh时，fi,j=maxh也一定成立，而C(i,j)的成长是很快的，当i=2时，C(2,sqrt(2*h)+1)就已经与h同量级了。也就是说，f矩阵除了第一列有h项有意义，从第2列开始，每一列只有O(sqrt(2*h)项有意义，如果对第一列特别处理一下（这一列实际上是可以直接求得的），那么要计算的量就是O(sqrt(2*h)*n)，而n又不超过log2h，所以时间复杂度也就只有O(sqrt(h)*log2h）了。6.7 优盘质量本题巧妙的应用了，对于一定量的优盘数，当高度在一定范围时，扔的次数是一样的冗余，这些状态可以说是无效状态。本题通过改变状态，只求有本质不同的状态，从而大大减少了计算量。总结2进制状态压缩DP的特点：状态中的某一维会比较小，一般不会超过15，多了的话状态数会急剧上升而无法压缩，一般来说需要状态压缩的也就是这一维。Q&AThank You for your time!
