ACM动态规划入门.ppt

《ACM动态规划入门.ppt》由会员分享，可在线阅读，更多相关《ACM动态规划入门.ppt（32页珍藏版）》请在三一办公上搜索。

1、ACM程序设计,谢勇,2023/7/5,2,今天，,你 AC吗？,依然没有,2023/7/5,3,第四讲,动态规划入门（Dynamic programming）,2023/7/5,4,一、经典问题：数塔问题,有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。,2023/7/5,5,用暴力的方法，可以吗？,2023/7/5,6,这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（230=10243 109=10亿）。,试想一下：,2023/7/5,7,拒绝暴力，倡导和

2、谐,2023/7/5,8,从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。如数字2，只要选择它下面较大值的结点19前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。结论：自顶向下的分析，自底向上的计算。,考虑一下：,2023/7/5,9,二、经典问题：最长有序子序列,2023/7/5,10,解决方案：,2023/7/5,11,思考 1160 FatMouses Speed,Sa

3、mple Input6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900,Sample Output4 4 5 9 7,2023/7/5,12,再思考（1087）,Super Jumping!Jumping!Juping!,解题思路？,2023/7/5,14,三、经典问题：最长公共子序列,HDOJ-1159：Sample Inputabcfbc abfcabprogramming contest abcd mnp,Sample Output 4 2 0,2023/7/5,

4、15,辅助空间变化示意图,2023/7/5,16,f(i,j)=由于f(i,j)只和f(i-1,j-1),f(i-1,j)和f(i,j-1)有关,而在计算f(i,j)时,只要选择一个合适的顺序,就可以保证这三项都已经计算出来了,这样就可以计算出f(i,j).这样一直推到f(len(a),len(b)就得到所要求的解了.,f(i-1,j-1)+1(ai=bj),max(f(i-1,j),f(i,j-1)(ai!=bj),子结构特征：,2023/7/5,17,四、经典问题：1421 搬寝室,Sample Input 2 1 1 3Sample Output 4,2023/7/5,18,搬寝室是很累

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

6、就是最低的疲劳度),请告诉他吧.,2023/7/5,19,第一感觉：,根据题目的要求，每次提的两个物品重量差越小越好，是不是每次提的物品一定是重量相邻的物品呢？,证明：假设四个从小到大的数：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(略),2023/7/5,20,预备工作：,排序！,2023/7/5,21,第二感觉：,对于一次操作，显然提的物品重量越接近越好，是不是可以贪心呢？请思考,考虑以下情况：1 4 5 8 10 11,什么结论？,2023/7/5,22,详细分析：,从最简单的情况考

7、虑：2个物品选一对，结论显然,结论？,4个物品选一对？（如何利用前面的知识）,3个物品选一对，,n个物品选一对，,最终问题：n个物品选k对，如何？（n=2k）,n个物品选二对，,2023/7/5,23,f(i,j)表示前j个取i对最小的疲劳度f(i,j)=min(f(i,j-1),f(i-1,j-2)+(item(j)-item(j-1)2),2023/7/5,24,五、经典问题：1058 Humble Numbers,Problem Description A number whose only prime factors are 2,3,5 or 7 is called a humble

8、number.The sequence 1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,.shows the first 20 humble numbers.Write a program to find and print the nth element in this sequence,2023/7/5,25,算法分析：典型的DP!,1-?,1-2=min(1*2,1*3,1*5,1*7),1-2-3=min(2*2,1*3,1*5,1*7),1-2-3-4=min(2*2,2*3,1*5,1*7),1-2-3-4-5=min(3*2,

9、2*3,1*5,1*7),2023/7/5,26,状态转移方程？,F(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7)(ni,j,k,m)特别的：i,j,k,m 只有在本项被选中后才移动,2023/7/5,27,关键问题：,这个题目的哪些经验值得我们借鉴？,2023/7/5,28,思考：免费馅饼,2023/7/5,29,如何解决？,请发表见解,2023/7/5,30,如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。,小结：DP的基本思想,2023/7/5,31,课后任务：,ACM程序设计作业（4）ACM程序设计 作业 1-3请补交,2023/7/5,32,该加油了,