ACM动态规划入门课件.ppt

1、ACM程序设计程序设计谢勇ericxiesina2022-8-82今天，今天，你你 ACAC吗？吗？依然没有2022-8-83第第四四讲讲动态规划入门动态规划入门（Dynamic programmingDynamic programming）2022-8-84一、一、经典问题经典问题：数塔问题数塔问题 有形如下图所示的数塔，从顶部出发，在每有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。层，要求找出一条路径，使路径上的值最大。2022-8-85用用暴力暴力的方法，可以吗？的方法，可

2、以吗？2022-8-86这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（230=10243 109=10亿）。试想一下：试想一下：2022-8-87 拒绝拒绝暴力，暴力，倡导倡导和谐和谐2022-8-88从顶点出发时到底向左走还是向右走应取决于是从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走向又要取决于再下一层上的最同样，下一层的走向又要取决

3、于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。直到倒数第二层时就非常明了。如数字如数字2，只要选择它下面较大值的结点，只要选择它下面较大值的结点19前进前进就可以了。所以实际求解时，可从底层开始，层层递就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。进，最后得到最大值。结论：自顶向下的分析，自底向上的计算。结论：自顶向下的分析，自底向上的计算。考虑一下：考虑一下：2022-8-89二、二、经典问题经典问题：最长有序子序列：最长有序子序列I012345678NumI147258369202

4、2-8-810解决方案：解决方案：I012345678NumI147258369FI1232343452022-8-811思考思考 11601160 FatMouses Speed FatMouses Speed Sample Input6008 1300 6008 1300 6000 2100 6000 2100 500 2000 500 2000 1000 4000 1000 4000 1100 3000 1100 3000 6000 2000 6000 2000 8000 1400 8000 1400 6000 1200 6000 1200 2000 1900 2000 1900 Sam

5、ple Output4 4 5 9 72022-8-812再再思考思考（10871087）Super Jumping!Super Jumping!Jumping!Jumping!Juping!Juping!解题思路？解题思路？2022-8-814三、三、经典问题经典问题：最长公共子序列：最长公共子序列HDOJ-1159HDOJ-1159：Sample Inputabcfbc abfcababcfbc abfcabprogramming contest programming contest abcd mnp abcd mnp Sample OutputSample Output 4 4 2 2

6、 0 02022-8-815a ab bc cf fb bc ca a1 11 11 11 11 11 1b b1 12 22 22 22 22 2f f1 12 22 23 33 33 3c c1 12 23 33 33 34 4a a1 12 23 33 33 34 4b b1 12 23 33 34 44 4辅助空间变化示意图辅助空间变化示意图2022-8-816f(i,j)=n由于f(i,j)只和f(i-1,j-1),f(i-1,j)和f(i,j-1)有关,而在计算f(i,j)时,只要选择一个合适的顺序,就可以保证这三项都已经计算出来了,这样就可以计算出f(i,j).这样一直推到f(l

7、en(a),len(b)就得到所要求的解了.f(i-1,j-1)+1(ai=bj)max(f(i-1,j),f(i,j-1)(ai!=bj)子结构特征：子结构特征：2022-8-817四四、经典问题经典问题：14211421 搬寝室搬寝室Sample InputSample Input 2 1 2 1 1 31 3Sample OutputSample Output 4 42022-8-818n搬寝室是很累的,xhd深有体会.时间追述2019年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物 品,xhd开始发呆,因为n是一个小于2000的整数,实在是太

8、多了,于是xhd决定随便搬2*k件过去就行了.但还是会很累,因为2*k也不小是一个不 大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)2=9.现在可怜的xhd希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧.2022-8-819第一感觉：第一感觉：n根据题目的要求，每次提的两个物根据题目的要求，每次提的两个物品重量差越小越好，是不是每次提品重量差越小越好，是不是每

9、次提的物品一定是重量相邻的物品呢？的物品一定是重量相邻的物品呢？n证明：假设四个从小到大的数：a、b、c、d，只需证明以下表达式成立即可：n(a-b)2+(c-d)2(a-c)2+(b-d)2n(a-b)2+(c-d)2=2k）nn个物品选二对，个物品选二对，2022-8-823nf(i,j)表示前j个取i对最小的疲劳度nf(i,j)=min(f(i,j-1),n f(i-1,j-2)+(item(j)-item(j-1)2n )2022-8-824五、五、经典问题经典问题：1058 1058 Humble NumbersHumble NumbersProblem Description Pr

10、oblem Description A number whose only prime factors are 2,3,5 A number whose only prime factors are 2,3,5 or 7 is called a humble number.The or 7 is called a humble number.The sequence 1,2,3,4,5,6,7,8,9,10,12,sequence 1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,.14,15,16,18,20,21,24,25,27,.sh

11、ows the first 20 humble numbers.shows the first 20 humble numbers.Write a program to find and print the nth Write a program to find and print the nth element in this sequence element in this sequence 2022-8-825算法分析算法分析：典型的：典型的DP!n1-?n1-2=min(1*2,1*3,1*5,1*7)n1-2-3=min(2*2,1*3,1*5,1*7)n1-2-3-4=min(2*

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