动态规划习题精讲.doc

信息学竞赛中的动态规划专题信息学竞赛中的动态规划专题哈尔滨工业大学 周谷越【关键字】动态规划 动机 状态 典型题目 辅助方法 优化方法【摘要】本文针对信息学竞赛（面向中学生的Noi以及面向大学生的ACM/ICPC）中的动态规划算法，从动机入手，讨论了动态规划的基本思想和常见应用方法。通过一些常见的经典题目来归纳动态规划的一般作法并从理论上加以分析和说明。并介绍了一些解决动态规划问题时的一些辅助技巧和优化方法。纵观全文可知，动态规划的关键在于把握本质思想的基础上灵活运用。【目录】1.动态规划的动机和基本思想1.1.解决重复子问题1.2.解决复杂贪心问题2.动态规划状态的划分方法2.1.一维状态划分2.2.二维状态划分2.3.树型状态划分3.动态规划的辅助与优化方法3.1.常见辅助方法3.2.常见优化方法4.近年来Noi动态规划题目分析4.1 Noi2005瑰丽华尔兹4.2 Noi2005聪聪与可可4.3 Noi2006网络收费4.4 Noi2006千年虫附录 参考书籍与相关材料1.动态规划的动机和基本思想首先声明，这里所说的动态规划的动机是从竞赛角度出发的动机。1.1 解决重复子问题对于很多问题，我们利用分治的思想，可以把大问题分解成若干小问题，然后再把各个小问题的答案组合起来，得到大问题的解答。这类问题的共同点是小问题和大问题的本质相同。很多分治法可以解决的问题（如quick_sort，hanoi_tower等）都是把大问题化成2个以内的不相重复的小问题，解决的问题数量即为(log2n / k)。而考虑下面这个问题：USACO 1.4.3 Number Triangles22/problem.php?id=1417【题目描述】考虑在下面被显示的数字金字塔。写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每一步可以走到左下方的点也可以到达右下方的点。73 88 1 02 7 4 44 5 2 6 1在上面的样例中，从7到3到8到7到5的路径产生了最大和：30。【输入格式】第一个行包含 R(1= R FI-1,J-1 ThenFI,J = FI-1,J + AI,JElseFI,J = FI-1,J-1 + AI,J接下来我们从理论上来讨论使用动态规划的条件。对于一种状态划分的方法来说，状态只与状态本身的性质有关，而与如何达到该状态等其他条件一概无关的性质叫做无后效性。由于存在无后效性，决策只能从决策本身的性质来确定，使得某一阶段的状态只与它所在阶段的前一阶段的状态有关。可以看出，存在无后效性是应用动态规划的前提条件。而考虑动态规划的正确性时，问题则需要满足最优子结构。所谓最优子结构，即当前一阶段的状态最优时，通过状态转移方程得到的状态也能达到最优。理论上看，无后效性和最优子结构是使用动态规划时的两个基本条件，而具体应用动态规划时更多凭借的是经验。下面再引出一道经典题目做一下分析：ACM/ICPC Shanghai2001 Skiing22/problem.php?id=1862【题目描述】滑雪是一项很受欢迎的体育运动，为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡。我们想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9我们可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-.-3-2-1更长。事实上，这是最长的一条。【输入格式】输入的第一行表示区域的行数R和列数C(1 = R,C = 500)。下面是R行，每行有C个整数，代表高度h，0=h 0 ThenReturn ArrI,JInt P, Ans = 0For P = 1 to 4 DoIf (I+DXP,J+DYP) In Map) And (HI+DXP,J+DYP HI,J) ThenIf (Ans FI+DXP,J+DYP)Ans = FI+DXP,J+DYPArrI,J = Ans + 1Return ArrI,J同样是动态规划，是什么使得两道题目代码的主干部分相差巨大呢？这里讨论一下动态规划的两种实现形式递推和记忆化搜索。首先，可以说所有用递推实现的动态规划均可以利用记忆化搜索实现。而某些题目之所以可以用递推求解，是因为这类题目同一阶段的状态表示上有很大的相关性，比如数字矩阵中某一行或列，这使得我们可以计算一个阶段的所有状态后再计算下一状态。而某些题目中利用动态规划划分的同一阶段的状态表示上没有多大相关性，比如Skiing里面的状态，从某点做起点每滑动一步为一个阶段，我们无法用一个准确的可以直接利用的集合将一个阶段中的状态表示出来，只能从已知状态去找和它相关联的状态。对于Skiing我们已知的是目标状态（即四面都不比该点高的点），通过边界条件（即四面都比该点高的最优值为1），便可以进行记忆化搜索。利用递推实现动态规划时，单位操作时间小，可以方便地使用一些优化；而利用记忆化搜索实现动态规划时，单位操作时间大，但可以避免计算一些不必要的状态。总地来说，相比于用状态空间搜索的方法解决这类存在重复子问题的题目，使用动态规划增大了空间的开销，但提高了时间效率。1.2 解决复杂贪心问题接下来，进入下一话题。我们考虑一下我们熟知的贪心算法和动态规划的关系，我看过很多写贪心算法和动态规划之间区别的材料，在这里我们不谈这个，而是要讨论动态规划与贪心算法之间的联系。如果我们把每一步贪心作为一个阶段，那么可以认为每个阶段只有一个状态，再把贪心策略看作状态转移方程，那么这样是否也是一种“动态规划”呢？实际上，它们二者之间的差别就在数据的维护上，有很多贪心问题在采取一次贪心策略之后要对数据进行全盘的维护，而我们讲的动态规划一般没有这个步骤。而这个维护的目的是什么呢？是为了保证正确性，和动态规划中的最优子结构的目的一样，那么就说明目前的状态划分不具有最优子结构，那么我们是否能够通过改变状态的划分方法来代替这个维护并使新划分的状态具有最优子结构呢？这里直接给出结论：对于某些分步讨论的贪心决策问题，我们可以通过扩展状态使之能够用动态规划解决。扩展出的状态的作用就是为了保证正确性，也就是保证最优子结构。举一个简单的例子：给出N个数，要从其中取M个求和，并使和尽量大。这明显是一个贪心可解的问题，把数字从大到小排序后取前M个求和即可。那么我们同样也可以扩展出一部分状态。我们设FI,J表示前I个数字中取了J个数字得到的最大和，则有：FI,J = Max (FI1,J,FI-1J-1 + AJ)。那些贪心算法并不用考虑的“多余”状态就是扩展出的状态，举个实例来说明：N = 5 , M = 3时，A = 1, 2, 3, 4, 5。那么显然1和2都不会被取到，但数组F中的F1,1, F2,1 和F2,2都是由1和2组成的状态，从贪心的角度看，它们就是多余的，就是为了使用动态规划扩展出来的状态。当然，就这道题目来看，贪心算法无论是从思维角度、编程角度还是时空复杂度角度都明显优于动态规划。HCPC Spring 2007 Hurdles Race/hoj/problem/view?id=2476【题目描述】自从刘翔在雅典夺得110米栏冠军之后，国人对跨栏比赛的关注程度大大提高。阿月和同学们经常在一起讨论刘翔需要用多少步来完成比赛，大家对该问题的意见不太一致，经常为此争论不休。我们下面定义这样一种跨栏比赛：tl表示起点到终点的距离（可能不是110）；sl表示刘翔一步可以跨越的最大距离（我们规定刘翔每次跨越的距离必需是整数）；fl表示第一个栏到起点的距离（fltl）；n表示栏的数目；d表示每两个栏之间的距离（我们保证最后一个栏到起点的距离小于tl）；每次跨栏的时候，刘翔都要保证栏的位置恰好在他跨越距离的正中间。求在这些条件下刘翔完成比赛所需要的最小步数。【输入格式】输入包括五个正整数，分别表示tl,sl,fl,n,d（tl不超过10000，sl不超过10）。【输出格式】输出包括一个整数，即刘翔完成比赛所需要的最小步数。【样例输入】110 3 20 10 5【样例输出】41【样例说明】起点到跨过第一个栏至少需要8步，之后每跨一个栏至少需要2步，从跨过最后一个栏到终点至少需要15步。由于只有跨栏的那步有限制条件，其它步没有，故有了贪心思想跨栏那步要尽可能的大。通过分情况讨论后得到解：跨第一个栏之前的步数 + 栏的个数 + 跑2个栏之间路程需要的步数 （栏的个数 - 1） + 最后一个栏需要的步数。需要考虑的特殊情况只有跨第一个栏的步长未必可以达到跨其它栏的步长。当然，如果比赛的时候可以快速地想到这个方法是最好不过的。实际上，使用动态规划更容易建立方程。设FI表示到达i位置所需要的最小步数，则有Fi=minFI-K+1，K=1.sl，其中I-K到I之间没栏；而有栏时，FI=minFI-2*sp+1,FI，sp为栏到i点距离。AsyzOI2007 营养膳食22/problem.php?id=1864【题目描述】阿月正在女朋友宁宁的监督下完成自己的增肥计划。为了增肥，阿月希望吃到更多的脂肪。然而也不能只吃高脂肪食品，那样的话就会导致缺少其他营养。阿月通过研究发现：真正的营养膳食规定某类食品不宜一次性吃超过若干份。比如就一顿饭来说，肉类不宜吃超过1份，鱼类不宜吃超过1份，蛋类不宜吃超过1份，蔬菜类不宜吃超过2份。阿月想要在营养膳食的情况下吃到更多的脂肪，当然阿月的食量也是有限的。【输入格式】输入第一行包含三个正整数n（n200）,m（m100）和k（k100）。表示阿月每顿饭最多可以吃m份食品，同时有n种食品供阿月选择，而这n种食品分为k类。第二行包含k个不超过10的正整数，表示可以吃1到k类食品的最大份数。接下来n行每行包括2个正整数，分别表示该食品的脂肪指数ai和所属的类别bi，其中ai100，bik。【输出格式】输出一个数字即阿月可以吃到的最大脂肪指数和。【样例输入】6 6 33 3 215 115 210 215 210 25 3【样例输出】60用贪心算法解决，就是把食品按脂肪指数排序后，在满足约束条件的情况下从大的开始吃，每吃一个更新一下约束条件。而用动态规划思想解决的话，可以设FI,J表示前I类食品一共吃J份能够获得的最大脂肪数和。则有FI,J = Max FI-1,K + GI,J-K，其中GI,J表示第I类食品种脂肪数最大的J份的和（也是要排序的）。Noip1999 旅行家的预算22/problem.php?id=1523【题目描述】一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）。每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格 Pi（i=l,2,.,N）。如果无法到达目的地，则输出“No solution”。否则输出最小费用，计算结果四舍五入至小数点后两位。【样例输入】275.6 11.9 27.4 2.8 21 102.0 2.92 220.0 2.2【样例输出】26.95我们假设现在在第I站，那么可知在该站加满油可以到达的最远距离。如果在这个范围内存在一个加油站J，它的价格比I便宜，那么只要把油加到刚好能到达第一个出现的J即可；否则就在I加满油，选择范围内最便宜的加油站J，开到J再做决策。如果觉得这个方法不是很好想的话，就用动态规划实现之。设FI,J表示到达第I个加油站油量为J需要的最小费用，则有FI,J = Min FI-1, J-K-G(I-1,I) + K*AI，其中G(I-1,I)表示第I个加油站和前一个加油站间的距离，AI表示第I个加油站的油价。对于以上三道题目，实现贪心更容易，而想到动态规划更容易（前提是对动态规划足够熟练），可以根据实际情况选择合适的算法。下面再给出两个相对复杂的题目。AsyzOI2005 雇工【题目描述】一中搬到新校舍，值得庆祝。但我们亲爱的电教老师FJ（Feng Jun not Farmer John）却遇到了个麻烦事。科技馆还没完全建好，需要雇人来完成一些后续工作。现在的行情是这样的：你雇佣一个人得给A元，解雇一个人得给人家B元（精神损失费），当然还有工资，每月K元。有一系列工作，需要N月来完成。当然，不是每个月都需要相同的人数。可是当你雇佣一个雇工，不管他干不干活，都得给他工资（吃大锅饭）。说明一下：到期的时候是不用付精神损失费的。请你帮帮FJ老师，他心系学校，绝对要为一中省钱。【输入格式】输入包含三行。第一行为N（不大于12的正整数）。第二行有三个数，A，K，B （J均不大于100）。第三行为每个月需要的最少人数（均小于1000）。【输出格式】输出包括一个数字即最小费用。【样例输入】34 5 610 9 11【样例输出】199考虑每一个月，比较当前的工人数M1和下一个月所需要的工人数M2，若M1M2，则必须雇佣缺少的工人，当然也不会多雇。问题的关键就在于可以解雇的时候解雇多少工人，可以认为对于一组给定的A,K和B就可以得到一个吃大锅饭的最长时间（超过该时间可以解雇了后再雇佣），这样我们找到这个时间内的最大工人需求量M3，若M1M3，那么不用解雇任何工人，否则就要解雇M1 - M3个工人。需要注意的是，判断最长时间时需要考虑到期的时候不付精神损失费的特殊情况。而采用动态规划则要简单得多。设FI,J表示完成了前I个月的工作任务且第I个月有J个工人所需的最小费用，则有FI,J = Min FI-1,H + G(H,J) + K*J，其中G(H,J)表示由H个工人变化到J个工人所要支付的费用（或雇佣或解雇）。使用动态规划来解决这道题目，无论从思路还是实现来说都要比贪心算法简单。在有规定时间限制的竞赛中，做题的速度也很重要。这催生了我们使用动态规划的第二个动机解决复杂的分步讨论的贪心决策问题。但仅限于数据范围不大的情况，因为较比贪心算法，动态规划的时间复杂度要大一些。总地来说，这类动态规划牺牲了程序的时空效率，但思维和编程比较简单，可以节约宝贵的竞赛时间。2.动态规划的状态划分方法在这里我们把动态规划状态的划分方法分为3种：一维状态划分、二维状态划分和树型状态划分。树型动态规划是由于树这种数据结构的特殊性衍生出来的（放在最后说），这里先讨论一下一维状态划分和二维状态划分的动态规划。前面提到的动态规划基本都属于一维状态划分，以Number Triangles的方程为例（FI,J表示从顶层走到第I行第J列的点能取得的最大和）。定义I为阶段变量，J为状态变量（我为了自圆其说，方便讲解，自己定义的），阶段变量可以确定状态所在阶段，而状态变量则反映状态本身的性质。允许只有阶段变量没有状态变量，例如Hurdles Race里的FI。而前面提到的二维状态划分只有Skiing一题（FI,J表示滑到第I行第J列的点时存在的最长滑坡长度），因为这里I和J两个变量才能确定状态所在的阶段。2.1.1 典型的线性动态规划我们通常说的线性动态规划就是一维状态划分的没有状态变量的动态规划。下面了列举几个典型的线性动态规划题图：UVA 10684 The Jackpot【题目描述】某人想迅速变得富有，但是他还不想工作。于是他开始赌博，存在一个奖金序列（有正有负），他想从中赢得最多的钱，我们规定他中途只可以退出一次（退出后不可以再回来）。【输入格式】输入第一行包含一个正整数N（N10000），接下里包含N个整数，它们的绝对值都不超过1000。【输出格式】输出该人能赢得的最大钱数。【样例输入】512 -4 -10 4 9【样例输出】13我们称该类问题为最大连续数字和。设FI表示到I为止（必须含AI）的最大连续整数和，如果FI-1为负数，那么显然FI = AI，否则有FI = FI-1 + AI。这样就构造出一个线性动态规划算法了，以下是它的一个经典应用：NECPC2007 Sum Of SubRectangular Parallelepiped/index.php?act=problem&id=1229【题目描述】现有一个棱长为n的立方体，可以分成n3个1*1*1的单位立方体。每个单位立方体都有一个整数值。现在要求在这个立方体找到一个包含完整单位立方体的长方体，使得该长方体内所有单位立方体的数和最大。【输入格式】第一行包含一个整数n。接下来n个n2的数字矩阵，每个数字矩阵代表一层，每个数字代表一个单位立方体的整数值。【输出格式】输出仅包括最大的长方体的数和。【样例输入】21 22 1-1 2-2 -1【样例输出】6最基础的方法是“直译”枚举过程，时间复杂度O（n9）。而记录先前考察的结果。如图所示，在统计长方体2时，只要将长方体1的统计结果加上长方体3就可以了，而不必按上述算法那样重新进行计算。经过这样的优化，利用了前面的计算结果，时间复杂度降为O（n8）。而对于每个平面的矩形有一种经典的压缩方法，设recx,y,z表示z轴坐标为z的水平面中矩形（1,1,x,y）的数和。则z轴坐标为z的水平面中左上角为（x1,y1）、右下角为（x2,y2）的矩阵的数和为recx2,y2,z + recx1,y1,z - recx2,y1,z - recx1,y2,z。有了上面的关系式，我们下面要做的只是枚举z,x1,x2,y1,y2来查找最优解。对于每组固定的x1,x2,y1,y2，recz, x1,x2,y1,y2就等于z个数字，那么只要求它们的最大连续和就可以。总的时间复杂度为O（n5）。Noip2004 合唱队型【题目描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2，K，他们的身高分别为T1，T2，TK，则他们的身高满足T1.Ti+1TK（1iK）。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。【输入格式】第一行是一个整数N(2N106)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130Ti230)是第i位同学的身高(厘米)。【输出格式】只包含一个整数，就是最少需要几位同学出列。【样例输入】8186 186 150 200 160 130 197 220【样例输出】4首先只考虑左半部分的合唱队型，这种题目类型叫做最长上升子序列问题（LIS），最常规的算法是设FI表示前I个数字中（必须包含AI）的最长上升子序列的长度，状态转移方程为FI = Max FJ + 1，其中J0,I-1 且AJ AI。I和J都需要枚举，所以时间复杂度为O（n2）。实际上LIS有一种贪心算法，我们用数组GI记录当前长度为I的上升子序列的最后一个元素的最小值，那么GI将会是一个单调的序列。对于每一个AJ，只要在G序列中找到一个最大的I，使得GI N0时，n可以由若干S到T之间的正整数（包括S，T）组成。因此，将障碍点按升序排列，当两相邻障碍点之间距离较大时，可适当缩小两障碍点之间距离，但不影响最终结果。（特别地，当S=T时需要单独处理）针对每一组S和T都存在一个N0。对于任意的S和T（ST时），那么每次至少有T和T-1两种跳法。假设青蛙跳T次，其中K次跳T步，T-K次跳T-1步，那么总步数为KT + (T-K)(T-1)= T(T-1) + K，也就是说T(T-1)以外的所有点都可以跳到。这样一来，我们就可以把间距超过T(T-1) + K的两点间距离化为T(T-1) + K。T=K=10时，T(T-1) + K取得最大值100，这时整个算法的时间复杂度为O(100MT)，可以在1s内通过全部测试数据。2.1.3 一维状态划分的非线性动态规划下面要讨论的是一维状态划分的非线性动态规划问题。其中最为经典的模型就是0-1背包问题：给定N种物品和一背包。物品I的重量是WI，其价值为VI，背包的容量为C。选择装入背包的物品，使得装入背包中物品的总价值最大，求这个最大价值。每考虑一件物品为一个阶段，对于每一物品来说，都只有取和不取两种可能。那么设FI,J表示考虑前I个物品取的总重量不超过J的最大价值，则有状态转移方程：FI,J = Max （FI-1,J, FI-1,J-WI + VI）。实际上，0-1背包问题和Number Triangles问题只是在做决策时略有不同，前者考虑取或者不取，而后者考虑要走到左边还是右边。最后提醒一下，0-1背包是一个NP问题，时空复杂度均为O（NW），当W的规模比较大时（不是很过分的大），空间开销随之增大，我们可以利用滚动数组解决这一问题。由于动态规划的无后效性，我们只需记录相邻的两个阶段的状态即可，这就是滚动数组的原理。Noip2006 金明的预算方案22/problem.php?id=1579【题目描述】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子： 主件 附件 电脑 打印机，扫描仪 书柜 图书 书桌 台灯，文具 工作椅无 如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为： vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*为乘号） 请你帮助金明设计一个满足要求的购物单。 【输入格式】 第1行为两个正整数，用一个空格隔开： N 和m，（其中N（32000）表示总钱数，m（60）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数v ,p 和q 。（其中v表示该物品的价格（v0，表示该物品为附件，q是所属主件的编号）【输出格式】 只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（200000）。 【样例输入】 1000 5800 2 0400 5 1300 5 1400 3 0500 2 0【样例输出】 2200题目已经提示我们每个主件可以有0个，1个或2个附件。那么考虑每套主件与附件的组合，最多有5种处理方法：不取，主件，主件+附件A，主件+附件B和主件+附件A+附件B。设FI,J表示前I种组合花费为J获得的最大重要度乘积和，则有：FI,J = Max (FI-1,J,FI-1,J-VI,0+VI,0*WI,0,FI-1,J-VI,0-VI,1+VI,0*WI,0+VI,1*WI,1,FI-1,J-VI,0-VI,2+VI,0*WI,0+VI,2*WI,2,FI-1,J-VI,0-VI,1-VI,2+VI,0*WI,0+VI,1*WI,1+VI,2*WI,2)还可以利用“每件物品都是10元的整数倍”的条件，总的时间复杂度为O（NM）。NoiWC2007 Hotel【题目描述】有N个男人，M个女人，其中有C（1CM,N500）对夫妇要住房。现在有P（P500)个房子。每个房子有个费用Ci和床位Bi（Bi5）。住房有以下要求：1.每个房子住的人数不能超过Bi2.一个房间住了夫妇，不能再住其他人。3.不考虑夫妇情况下：一个房间住了男人后，不能再住女人。对女人也是一样。求这N+M个人住房的最少费用。【输入格式】 第1行为四个正整数，N,M,C和P。以下P行每行包含两个正整数Ci和Bi。【输出格式】 只有一个正整数，为这N+M个人住房的最少费用（longint范围内）。【样例输入】 3 2 2 430 420 110 220 2【样例输出】 40 事实上我们可以发现按照第2条住房的夫妇数不会超过1，如果有2对夫妇那么可以交换一下，在同样代价下反而能住更多人。这样我们可以枚举夫妇数（0或者1），这样就去掉了夫妇的这个限制。设FI,J,K表示前I个房间安排好后，还剩下J男K女的最小费用。则显然有FI,J,K=Min FI-1,J,K, FI-1,J+BI,K+CI, FI-1,J,K+BI+CI，时间复杂度为O(P M N)。和前面说过的Score Inflation一样，在人数比较多的时候可以加入贪心思想。当人数超过R的时候，性价比比较高的房间就必然会被使用，那么先把所有房间按照性价比排序然后按顺序分放直到人数少于R为止，时间复杂度就降为O(P R2)。Shanghai2004 The Horse Racing22/problem.php?id=1865【题目描述】中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马（N2000），每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢最多的钱？【输入格式】 第1行为一个正整数N。第2行和第3行每行包含N个正整数，分别表示田忌和齐王帐下马的速度。【输出格式】 只有一个正整数，即田忌能赢得的最大钱数。【样例输入】 392 83 7195 87 74【样例输出】 200这个问题很显然可以转化成一个二分图最佳匹配的问题。把田忌的马放左边，把齐王的马放右边。田忌的马A和齐王的B之间，如果田忌的马胜，则连一条权为200的边；如果平局，则连一条权为0的边；如果输，则连一条权为200的边，但二分图最佳匹配算法的复杂度为O（N3）。因为田忌掌握有比赛的主动权，他总是根据齐王所出的马来分配自己的马，所以这里不妨设齐王的出马顺序是按马的速度从高到低出的。对于这样的假设，我们归纳出如下贪心策略：1.如果田忌剩下的马中最强的马都赢不了齐王剩下的最强的马，那么应该用最差的一匹马去输给齐王最强的马；2.如果田忌剩下的马中最强的马可以赢齐王剩下的最强的马，那就用这匹马去赢齐王剩下的最强的马；这两点是显然的，关键在于田忌最快的马和齐王最快的马打平，那么田忌是选择平还是输呢？ 如果全部打平的话，如果齐王马的速度分别是1 2 3，田忌马的速度也是1 2 3，每次选择打平的话，田忌一分钱也得不到，而如果选择先用速度为1的马输给速度为3的马的话，可以赢得200两黄金。而如果全部输掉的话，如果齐王马的速度分别是1 3，田忌马的速度分别是2 3，田忌一胜一负，仍然一分钱也拿不到。而如果先用速度为3的马去打平的话，可以赢得200两黄金。这里虽然出现了分支，但我们得知田忌一定是将他马按速度排序之后，从两头取马去和齐王的马比赛。那先把田忌和齐王的马分别按从强到弱排序，设FI,J表示齐王按从强到弱的顺序出马和田忌进行了I场比赛之后，田忌从头取了J匹较强的马出战所能够得到的最大钱数。则有：FI,J = Max FI-1,J + GN-(I-J)+1,I,FI-1,J-1+GJ,I，其中GJ,I表示田忌的第J匹马和齐王的第I匹马比赛的获利。2.1.4 压缩状态的动态规划下面介绍一下压缩状态的动态规划。这种动态规划的本质是对集合进行动态规划，对于给出的数据在某一个或几个维度上一般具有比较小的范围（可以枚举一类的状态），我们把一个枚举出的状态视为一个集合，通过它们之间的关系（产生式规则）可以进行动态规划。当集合中元素个数的不定性或范围大时，如果直接开数组存，索引数组的编程复杂度太高（而且程序时间效率低下），所以要进行集合编码。一般利用数据的可枚举性，采用进位制的方法进行状态压缩。下面举一个经典的问题作为例子：Noi2001 炮兵阵地【题目描述】司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用H 表示），也可能是平原（用P表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示： 如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。【输入格式】 第一行包含两个由空格分割开的正整数，分别表示N和M；接下来的N行，每一行含有连续的M个字符(P或者H)，中间没有空格。按顺序表示地图中每一行的数据。N100；M10。【输出格式】 仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。【样例输入】 5 4PHPPPPHHPPPPPHPPPHHP【样例输出】 6 这是一道比较麻烦的问题，如果某点是P，就可以有放兵与不放兵两种方案，但对于在I和J位置之前的所有P的摆放方案有多种方案，我们将这两种方案分别去尝试与P(I,J)之前所有方案结合，则P(I,J)又会有很多种方案。考虑一个列为10（M的最大值）的表。即使是一个全为P的空列上一共也只有60种合法的炮兵放置方法。具体对一个列数为10的PH表而言，对每一列也只有前两列对其产生影响，我们设FI,X,Y来表示第I-1行处于第X种状态，第I行处于第Y种状态时，从首行扫描到该行时所能存放的最多的炮兵数。则有FI,X,Y = MaxFI-1,Z,X + NY，其中要求没有互相攻击的可能，NY表示方案Y对应的炮兵数。很多状态压缩动态规划是用二进制存储状态，比如有1到10共10个点，需要把它们都走一遍，走过1,2,3点的路径可以用00000001112=710表示，而走过1,2,3,5的路径可以用00000101112=2310表示。下面我们用位运算建立它们之间的联系，需要使用异或运算符（），0000010111200000100002=00000001112，即23(1(5-1) = 7，这大大方便了我们在状态压缩动态规划中进行状态转移。下面再举一个例子：HCPC Spring 2007 FishCanFly【题目描述】fish is not a common fish, he has a dream that he can fly someday. One day his friend wolfshow tells him a tale.It is said that there lives a magic bailey in the remote mountains. He can enable some fish to fly once a year. Every year many fish arrive at baileys house. The lucky fish is the one who has the highest score(what a bad thing!). There are several posthouses on the way to baileys house. One can get some score when he enters it. But if you enter the same posthouse several times, you can get the score only once. You must remember that the total time is limited. So if you cant get there in time, you will lose it.Luckily, wi