《HDU25道动态规划题的解题报告》由会员分享，可在线阅读，更多相关《HDU25道动态规划题的解题报告（12页珍藏版）》请在金锄头文库上搜索。
1、HDU 25道动态规划题的解题报告（有详细的思路，状态的描述，以及状态转移方程，但不会给出代码，请自己编码）密码：zafuA 最简单的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; Else Dpij=max(dpij-1,dpi-1j);C Dp经典问题，LIS,最长上升子序列。
3、首先介绍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 很简单的方法是，因为物品可以无限取，那么在背包容量一定的前提下，求费用最小的物品就是答案。
4、还有一种方法就是直接做完全背包，物品价值为1。M 这题也是赤果果的二维费用背包，不理解的再去看背包九讲，注意初始化，即考虑状态的意义，没有意义的状态使之不影响后面的状态。可以在装满的背包中逆序搜经验值大于升级所需，第一个搜到的就是答案。也可以在不装满的背包中搜整张表，经验值大于升级所需，并且所消耗体力最小。N 这题是比较详细的背包问法变化问题，求第K大背包。显然dpi记录的状态已经无法满足题目的需要，我们还是要从无后效性（即这个仅根据哪些特征决策）考虑如何描述这个问题，显然，对于每个背包容量都要保存前K大的值，这样才能进行状态转移。那么，可以用dpvk表示背包容量为i的第k大价值。显然dpv1
5、k这K个数是由大到小排列的，所以是一个有序序列。那么有这里有两个有序序列fi-ci1k+vi和fi1k，合并这两个有序序列并将结果（的前K项）储存到fi1k上，最后的答案就是fvk.O 这题是每组至少取一件的的背包。而分组背包的含义是每组最多取一件，我希望大家在做这题的时候，思路不要被分组背包限制住，虽然和分组背包最大的区别只是把物品遍历的顺序放到第二层上。而用常规dp状态转移的方式去考虑这个问题。 还是一样，先从无后效性去考虑描述问题的方式。这个问题显然是对于第i组物品的状态既可以从第i-1组来也可以从第i组来，而分组背包是状态只从i-1组来。（请仔细思考二者的区别）所以需要记录组别来进行状
6、态转移。 于是，我们可以用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，这题如果在独立思考的前提下，完全弄懂各种背包的联系区别，并不被其所限，你就可以去拯救世界了。这题的物品组
7、有三种情况，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); 看
8、着有点烦，但请仔细思考。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.这题与最长公共子序列有点类似。都是比较两个串各自的最后一个字符，首先要说明的
9、是向一个串中插入一个字符和向另一个串中删除一个字符其实是一样的，为了便于理解就舍掉插入的操作。显然，状态的描述和最长公共子序列类似，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. 这题其实就是求公共最长上升序列，只不过把字符变
