ACM算法 动态规划(1)

单击此处编辑母版样式,单击此处编辑幻灯片母版样式,第二层,第三层,第四层,第五层,*,*,*,ACM,程序设计,计算机学院 刘春英,11/1/2024,1,今天，,你,了吗？,AC,11/1/2024,2,每周一星（,3,）：,liuzewei,11/1/2024,3,第四讲,动态规划,(1),（,Dynamic programming,）,11/1/2024,4,先热身一下,11/1/2024,5,（,1466,）计算直线的交点数,问题描述,：,平面上有,n,条直线，且无三线共点，问这些直线能有多少种不同交点数。,输入：,n,（,n=20,）,输出,：每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数。,样例输入,4,样例输出,0 3 4 5 6,11/1/2024,6,思考,2,分钟,:,如何解决,?,11/1/2024,7,初步分析,:,我们将,n,条直线排成一个序列，,直线,2,和直线,1,最多只有一个交点，,直线,3,与直线,1,和直线,2,最多有两个交点,.,，,直线,n,和其他,n-1,条直线最多有,n-1,个交点，,由此得出,n,条直线互不平行且无三线共点的最多交点数,max=1+2+(n-1)=n(n-1)/2,但本题不这么简单，因为问题问的是：这些直线有多少种不同的交点数？,11/1/2024,8,容易列举出,N=1,2,3,的情况：,0,0,，,1,0,，,2,，,3,如果已知,无交点；,2,、,第四条与,其中两条平行，交点数为,(n-1,)*1+0=3;,3,、,第四条与,其中一条平行，这两条平行直线和另外两点直线的交点数为,(n-2)*2=4,而另外两条直线既可能平行也可能相交，因此可能交点数为：,（,n-2,）*,2+0=4,或者,(n-2)*2+1=5,4,、,第四条直线不与任何一条直线平行，交点数为：,(n-3)*3+0=3,或者,(n-3)*3+2=5,或者,(n-3)*3+3=6,即,n=4,时，有,0,个，,3,个，,4,个，,5,个，,6,个不同交点数。,11/1/2024,9,从上述,n=4,的分析过程中，我们发现：,m,条直线的交点方案数,=,（,m-r,）条平行线与,r,条直线交叉的交点数,+r,条直线本身的交点方案,=,（,m-r,）*,r+r,条之间本身的交点方案数（,1,=r 109=10,亿）。,11/1/2024,13,所以，不可以如此,暴力,！,11/1/2024,14,考虑一下：,从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。,同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。,如数字,2,，只要选择它下面较大值的结点,19,前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。,结论：自顶向下的分析，自底向上的计算。,11/1/2024,15,Understand?,11/1/2024,16,二、思考题：最长有序子序列,I,0,1,2,3,4,5,6,7,8,NumI,1,4,7,2,5,8,3,6,9,请回答：,穷举（暴力）方法的时间复杂度是多少？,11/1/2024,17,解决方案：,I,0,1,2,3,4,5,6,7,8,NumI,1,4,7,2,5,8,3,6,9,FI,1,2,3,2,3,4,3,4,5,11/1/2024,18,三、,HDOJ_1160,FatMouses,Speed,题目链接,Sample Input,6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900,Sample Output,4,4,5,9,7,11/1/2024,19,题目分析：,设,Micei.W,表示第,i,只老鼠的重量，,Micei.S,表示第,i,只老鼠的速度。我们先对,Mice,进行排序，以,W,为第一关键字，从小到大，,S,为第二关键字，从大到小。,设,fi,为,Micei,至,Micen,最长的序列长度。考虑某一个,fi,，,则有：,fi=max(fi,fj+1)(1=j Micej.W,，,Micei.S Micej.S),其中，初始条件为,fi=1(i=1,2,.,n),。,11/1/2024,20,Qestion,:,两个问题有本质区别吗？,11/1/2024,21,思考（期末考试题）：,Super Jumping!Jumping!Jumping!,11/1/2024,22,解题思路？,11/1/2024,23,四、,HDOJ_1159,Common Subsequence,题目链接,Sample Input,abcfbc,abfcab,programming contest,abcd,mnp,Sample Output,4 2 0,11/1/2024,24,请先计算暴力算法的时间复杂度：（当然是指最坏情况！）,？,11/1/2024,25,a,b,c,f,b,c,a,1,1,1,1,1,1,b,1,2,2,2,2,2,f,1,2,2,3,3,3,c,1,2,3,3,3,4,a,1,2,3,3,3,4,b,1,2,3,3,4,4,辅助空间变化示意图,11/1/2024,26,子结构特征：,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),11/1/2024,27,理论总结,11/1/2024,28,一、动态规划的基本思想,11/1/2024,29,如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。,一、动态规划的基本思想,11/1/2024,30,二、动态规划的基本步骤,动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。设计一个动态规划算法，通常可以按以下几个步骤进行：,11/1/2024,31,（,1,）找出最优解的性质，并刻画其结构特征。,（,2,）递归地定义最优值。,（,3,）以,自底向上,的方式计算出最优值。,（,4,）根据计算最优值时得到的信息，构造一个最优解。,其中（,1,）,（,3,）步是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（,4,）可以省去。若需要求出问题的一个最优解，则必须执行步骤（,4,）。此时，在步骤（,3,）中计算最优值时，通常需记录更多的信息，以便在步骤（,4,）中，根据所记录的信息，快速构造出一个最优解。,11/1/2024,32,三、动态规划问题的特征,动态规划算法的有效性依赖于问题本身所具有的两个重要性质：,1,、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。,2,、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。,11/1/2024,33,思考：,免费馅饼,11/1/2024,34,如何解决？,请发表见解,11/1/2024,35,Any Question?,11/1/2024,36,附录：,DP,练习题,(HDOJ),：,1003,、,1087,、,1159,、,1160,、,1176,1024,、,1025,、,1058,、,1069,、,1081,1074,、,1157,、,1158,、,1466,1078,、,1080,、,1114,1203,、,1294,、,1227,、,1223,1500,、,1501,、,1502,、,1503,1505,、,1506,、,1510,、,2059,11/1/2024,37,课后一定要练习！,DP”,相,-,当,-”,重要！,11/1/2024,38,有志于参加,竞赛,的同学，加油！,11/1/2024,39,ACM,天天见！,11/1/2024,40,