HDU25道动态规划题的解题报告.doc

HDU 25道动态规划题的解题报告（有详细的思路，状态的描述，以及状态转移方程，但不会给出代码，请自己编码）/webcontest/contest_show.php?cid=1264密码：zafuA 最简单的dp，但很重要。说明了动态规划产生的动机之一：递归产生的大量重复子问题。有两种解决方法，一、记忆化搜索，就是在用递归处理问题的过程中把已经算过的状态记录在一张表dp中，下一次需要重复计算时直接返回。二、自底向上的递推，可以理解为递推的逆过程，就是从最小的子问题去推导更大的子问题。dpij表示由该点i,j出发往下走的最大价值这题的状态转移方程显然是dpij=max(dpi+1j,dpi+1j+1);(最后一层直接返回该数)B dp经典问题LCS。还是思考如何把问题的规模缩小，那么我们首先取两个串各自的第一个或最后一个进行比较，可以进行最优操作（为什么，请思考）。情况一、两者相等，则取之作为最长公共子串，问题就转化为比较len1-1 、len2-1的最长公共子即可。情况二、两者不相等。则必然舍弃某一个的其中一个字符，再进行接下的比较。问题就转化为len1与len2-1比较，或者是len1-1与len2比较，取大者。dpij表示str1的前i个与str2的前j个的最长公共子串。状态转移方程、 If(str1i-1=str2j-1) Dpij=dpij+1; Else Dpij=max(dpij-1,dpi-1j);C Dp经典问题，LIS,最长上升子序列。首先介绍O(n2)的方法，对第i个数考虑，以找其前一个数为突破口，如果i的前一个数为j，那么问题就从找前i个数的LIS转化成找前j个数的LIS。Dpi表示前i个数的LIS数值 ，那么，Dpi=mindpj | (ajai)&1=j=dj&diaj)&1=j=(1-P)的最大的i。K 题意是由多件物品组成最相近的两个数，且物品个数一定。设物品的价值为W，有两种方法，一种是背包可以不装满，那么dpW/2和W-dpW/2就是答案。 另一种是将背包装满，只需要从W/2处开始遍历找到的第一个大于0的数就是答案。L 很简单的方法是，因为物品可以无限取，那么在背包容量一定的前提下，求费用最小的物品就是答案。还有一种方法就是直接做完全背包，物品价值为1。M 这题也是赤果果的二维费用背包，不理解的再去看背包九讲，注意初始化，即考虑状态的意义，没有意义的状态使之不影响后面的状态。可以在装满的背包中逆序搜经验值大于升级所需，第一个搜到的就是答案。也可以在不装满的背包中搜整张表，经验值大于升级所需，并且所消耗体力最小。N 这题是比较详细的背包问法变化问题，求第K大背包。显然dpi记录的状态已经无法满足题目的需要，我们还是要从无后效性（即这个仅根据哪些特征决策）考虑如何描述这个问题，显然，对于每个背包容量都要保存前K大的值，这样才能进行状态转移。那么，可以用dpvk表示背包容量为i的第k大价值。显然dpv1k这K个数是由大到小排列的，所以是一个有序序列。那么有这里有两个有序序列fi-ci1k+vi和fi1k，合并这两个有序序列并将结果（的前K项）储存到fi1k上，最后的答案就是fvk.O 这题是每组至少取一件的的背包。而分组背包的含义是每组最多取一件，我希望大家在做这题的时候，思路不要被分组背包限制住，虽然和分组背包最大的区别只是把物品遍历的顺序放到第二层上。而用常规dp状态转移的方式去考虑这个问题。 还是一样，先从无后效性去考虑描述问题的方式。这个问题显然是对于第i组物品的状态既可以从第i-1组来也可以从第i组来，而分组背包是状态只从i-1组来。（请仔细思考二者的区别）所以需要记录组别来进行状态转移。 于是，我们可以用dpij来表示取到前i组物品，背包容量为j所能获得的最大价值。状态转移方程、dpit=MAX(dpit-si.cj+si.vj,dpi-1t-si.cj+si.vj,dpit);/至少取一件，所以只能去，要么从第i组来，要么从第i-1组来。P 这题和M几乎是一样的，就是赋初值的时候要稍微注意点。（自己思考，就不再赘述了）Q 这题是赤果果的分组背包。详见背包九讲。三层循环。组别、容量、该组物品。（重在理解）R 这题是所选的背包题中最难的一道，也是本背包关的小BOSS，这题如果在独立思考的前提下，完全弄懂各种背包的联系区别，并不被其所限，你就可以去拯救世界了。这题的物品组有三种情况，0表示的是O的至少取一件的背包。1表示的是Q的常规分组背包，2表示的其实就是对该组物品做01背包。状态描述显然和O一样，用dpij来表示取到前i组物品，背包容量为j所能获得的最大价值。状态转移方程是:state=0 dpik=max(dpi-1k-jobi.cj+jobi.vj,dpik-jobi.cj+jobi.vj，dpik)State=1 Dpik=max(dpi-1k-jobi.cj+jobi.vj,dpik-jobi.cj+jobi.vj,dpik,dpi-1k);State=2Dpij=max(dpik,dpi-1j,dpi-1j-jobi.ck+jobi.vk); 看着有点烦，但请仔细思考。S接下来的问题就是常规的dp题了，而我们之所以讲了那么多的经典模型，就是为了更熟练地去处理这些常规的问题。这题的思路是先考虑出i-j段被一个邮局覆盖的最短距离和才能进行状态转移，对于这个问题，显然是建在i-j的终点所在的村庄上是最优的，就先不做证明了。这样我们就可以先预处理出任意i-j段被一个邮局覆盖的最短距离和用mapij表示。那么，dpij状态的描述是前i个村庄被j个邮局覆盖的最短距离和。状态转移方程显然是dpij=min(dpij,dpi-1j-k+mapj-k+1j)（1=k=j） T.这题与最长公共子序列有点类似。都是比较两个串各自的最后一个字符，首先要说明的是向一个串中插入一个字符和向另一个串中删除一个字符其实是一样的，为了便于理解就舍掉插入的操作。显然，状态的描述和最长公共子序列类似，dpij表示的是str1的前i个值转化为str2的前j个值。If(str1i-1=str2j-1) 那么要么转化成为前i-1个和前j-1个转化，或者删除其中一种If（str1i-1！=str2j-1） 那么要么change，要么删除其中一种于是状态转移方程：if(str1i-1=str2j-1) dpij=min(dpi-1j-1,dpij-1+1,dpi-1j+1);else dpij=min(dpi-1j-1+1,dpij-1+1,dpi-1j+1);U这题比较难考虑，因为有至少要学L分钟这个限制。很自然我们想到状态描述显然是dpij表示前i分钟已经睡了j分钟。状态转移方程也很容易推： 两种决策，要么睡，要么学习，而学习至少要学L分钟，那么dpij=maxdpi-1j-1,dpi-tj | L=t=j) max_jj=max(dpi-lj+sumi-sumi-l,max_jj+vi)V. 这题其实就是求公共最长上升序列，只不过把字符变成字符串。现在的问题是求出了dp之后，如何输出其中一个方案？ 往回找路径就可以了。有困难的话可以参考以下代码，最好还是独立思考自己完成 - - 。 while(len10&len20) if(dplen1len2=dplen1-1len2-1+1&strcmp(str1len1,str2len2)=0) strcpy(jilunum+,str1len1); len1-; len2-;else if(dplen1len2=dplen1-1len2) len1-;else len2-;W这题的难点在于初始化，状态的描述（怎么去思考我就不赘述了，请回忆上课讲过的东西）dpij表示str1的前i个和str2的前j个能否构成str的前i+j个，如果可以，赋值为1 否则为0.状态转移方程、If（str1i-1=stri+j-1&dpi-1j=1）|（str2j-1=stri+j-1&dpij-1=1） Dpij=1ElseDpij=0;这题的初始化是最重要的地方，请根据以上状态转移方程和状态的实际意义仔细考虑下。X状态的描述总是那么明显，dpij表示前i个数E-value恰好等于j的个数。那么，我们考虑添加一个数i，如果放在最后或者是和原来就是E-value的位置交换，那么E-value的个数肯定不边，（思考为什么），如果和原来不是E-value的数进行交换，那么个数-1（思考）。SOGA,这样一来状态转移方程就非常清晰了。