《ACM动态规划入门》PPT课件

《《ACM动态规划入门》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM程序设计谢勇ericxie@sina.com2021/7/211今天，你AC吗？依然没有2021/7/212第四讲动态规划入门（Dynamicprogramming）2021/7/213一、经典问题：数塔问题有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。2021/7/214用暴力的方法，可以吗？2021/7/215这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（2^30=102

2、4^3>10^9=10亿）。试想一下：2021/7/216拒绝暴力，倡导和谐～2021/7/217从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。如数字2，只要选择它下面较大值的结点19前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。结论：自顶向下的分析，自底向上的计算。考虑一下：2021/7/218

3、二、经典问题：最长有序子序列I012345678Num[I]1472583692021/7/219解决方案：I012345678Num[I]147258369F[I]1232343452021/7/2110思考1160FatMouse'sSpeedSampleInput60081300600021005002000100040001100300060002000800014006000120020001900SampleOutput445972021/7/2111再思考（1087）SuperJumping!Jumpin

4、g!Juping!2021/7/2112解题思路？2021/7/2113三、经典问题：最长公共子序列HDOJ-1159：SampleInputabcfbcabfcabprogrammingcontestabcdmnpSampleOutput4202021/7/2114abcfbca111111b122222f122333c123334a123334b123344辅助空间变化示意图2021/7/2115f(i,j)={由于f(i,j)只和f(i-1,j-1),f(i-1,j)和f(i,j-1)有关,而在计算f(i

5、,j)时,只要选择一个合适的顺序,就可以保证这三项都已经计算出来了,这样就可以计算出f(i,j).这样一直推到f(len(a),len(b))就得到所要求的解了.f(i-1,j-1)+1(a[i]==b[j])max(f(i-1,j),f(i,j-1))(a[i]!=b[j])子结构特征：2021/7/2116四、经典问题：1421搬寝室SampleInput2113SampleOutput42021/7/2117搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为

6、10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2*k件过去就行了.但还是会很累,因为2*k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)^2=9.现在可怜的xhd希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),

7、请告诉他吧.2021/7/2118第一感觉：根据题目的要求，每次提的两个物品重量差越小越好，是不是每次提的物品一定是重量相邻的物品呢？证明：假设四个从小到大的数：a、b、c、d，只需证明以下表达式成立即可：(a-b)^2+(c-d)^2<(a-c)^2+(b-d)^2(a-b)^2+(c-d)^2<(a-d)^2+(b-c)^2……(略)2021/7/2119预备工作：排序！2021/7/2120第二感觉：对于一次操作，显然提的物品重量越接近越好，是不是可以贪心呢？请思考…考虑以下情况：14581011什么结论？202

8、1/7/2121详细分析：从最简单的情况考虑：2个物品选一对，结论显然结论？4个物品选一对？（如何利用前面的知识）3个物品选一对，…n个物品选一对，…最终问题：n个物品选k对，如何？（n>=2k）n个物品选二对，…2021/7/2122f(i,j)表示前j个取i对最小的疲劳度f(i,j)=min(f(i,j-1),f(i-1,j-