《HDU25道动态规划题的解题报告》由会员分享，可在线阅读，更多相关《HDU25道动态规划题的解题报告（12页珍藏版）》请在金锄头文库上搜索。
1、HDU 25 道动态规划题的解题报告（有详细的思路，状态的描述，以及状态转移方程，但不会给出代码，请自己编码）http:/ 最简单的 dp，但很重要。说明了动态规划产生的动机之一：递归产生的大量重复子问题。有两种解决方法，一、记忆化搜索，就是在用递归处理问题的过程中把已经算过的状态记录在一张表 dp中，下一次需要重复计算时直接返回。二、自底向上的递推，可以理解为递推的逆过程，就是从最小的子问题去推导更大的子问题。dpij表示由该点 i,j 出发往下走的最大价值这题的状态转移方程显然是dpij=max(dpi+1j,dpi+1j+1);(最后一层直接返回该数)B dp 经典问题 LCS。还是思考
2、如何把问题的规模缩小，那么我们首先取两个串各自的第一个或最后一个进行比较，可以进行最优操作（为什么，请思考） 。情况一、两者相等，则取之作为最长公共子串，问题就转化为比较 len1-1 、len2-1 的最长公共子即可。情况二、两者不相等。则必然舍弃某一个的其中一个字符，再进行接下的比较。问题就转化为 len1 与 len2-1 比较，或者是 len1-1 与 len2 比较，取大者。dpij表示 str1 的前 i 个与 str2 的前 j 个的最长公共子串。状态转移方程、If(str1i-1=str2j-1)Dpij=dpij+1;ElseDpij=max(dpij-1,dpi-1j);C
3、 Dp 经典问题， LIS,最长上升子序列。首先介绍 O(n2)的方法，对第 i 个数考虑，以找其前一个数为突破口，如果 i的前一个数为 j，那么问题就从找前 i 个数的 LIS 转化成找前 j 个数的 LIS。Dpi表示前 i 个数的 LIS 数值 ，那么，Dpi=mindpj | (aj=dj&diaj)&1=(1-P) 的最大的 i。K 题意是由多件物品组成最相近的两个数，且物品个数一定。设物品的价值为 W，有两种方法，一种是背包可以不装满，那么 dpW/2和 W-dpW/2就是答案。 另一种是将背包装满，只需要从 W/2 处开始遍历找到的第一个大于 0 的数就是答案。L 很简单的方法是
4、，因为物品可以无限取，那么在背包容量一定的前提下，求费用最小的物品就是答案。还有一种方法就是直接做完全背包，物品价值为 1。M 这题也是赤果果的二维费用背包，不理解的再去看背包九讲，注意初始化，即考虑状态的意义，没有意义的状态使之不影响后面的状态。可以在装满的背包中逆序搜经验值大于升级所需，第一个搜到的就是答案。也可以在不装满的背包中搜整张表，经验值大于升级所需，并且所消耗体力最小。N 这题是比较详细的背包问法变化问题，求第 K 大背包。显然 dpi记录的状态已经无法满足题目的需要，我们还是要从无后效性（即这个仅根据哪些特征决策）考虑如何描述这个问题，显然，对于每个背包容量都要保存前K 大的值
5、，这样才能进行状态转移。那么，可以用 dpvk表示背包容量为 i 的第 k 大价值。显然 dpv1k这 K个数是由大到小排列的，所以是一个有序序列。那么有这里有两个有序序列 fi-ci1k+vi和 fi1k，合并这两个有序序列并将结果（的前 K 项）储存到 fi1k上，最后的答案就是 fvk.O 这题是每组至少取一件的的背包。而分组背包的含义是每组最多取一件，我希望大家在做这题的时候，思路不要被分组背包限制住，虽然和分组背包最大的区别只是把物品遍历的顺序放到第二层上。而用常规 dp 状态转移的方式去考虑这个问题。 还是一样，先从无后效性去考虑描述问题的方式。这个问题显然是对于第 i 组物品的状
6、态既可以从第 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 这题是所选
7、的背包题中最难的一道，也是本背包关的小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
8、.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 个村庄被
9、j 个邮局覆盖的最短距离和。状态转移方程显然是dpij=min(dpij,dpi-1j-k+mapj-k+1j)（1=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+,str1l
10、en1);len1-;len2-;else if(dplen1len2=dplen1-1len2)len1-;elselen2-;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个
11、数E-value恰好等于j的个数。那么，我们考虑添加一个数i，如果放在最后或者是和原来就是E-value的位置交换，那么E-value的个数肯定不边，（思考为什么），如果和原来不是E-value的数进行交换，那么个数-1（思考）。SOGA,这样一来状态转移方程就非常清晰了。dpij=(dpi-1j-1*(i-j)%mod+(dpi-1j*(j+1)%mod)%modW这题有点复杂，涉及的只是也有点多，来年的集训的最后一课，我打算当作例题给大家分析下，所以就先不写出解题报告了，感兴趣的同学可以先思考，如果有哪位大神可以直接做出，我也表示衷心的YM。That is all。希望大家好好思考动态规划，学好大学阶段最重要也是最精致的算法，请用力。
