ACM程序设计,杭州电子科技大学 刘春英 ,2020/9/7,2,今天，,你 了吗？,AC,2020/9/7,3,每周一星（3）：,混沌的云Knight,2020/9/7,4,第四讲,动态规划(1) （Dynamic programming）,2020/9/7,5,先热身一下,2020/9/7,6,(1466)计算直线的交点数,问题描述： 平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数 输入：n（n<=20） 输出：每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数 样例输入 4 样例输出 0 3 4 5 6,2020/9/7,7,初步分析:,我们知道: n条直线互不平行且无三线共点的最多交点数max=1+2+(n-1)=n(n-1)/2, 但本题不这么简单，因为问题问的是：这些直线有多少种不同的交点数？,2020/9/7,8,思考2分钟:如何解决?,,2020/9/7,9,然后，假设<=n-1的情况都已经知道,分析思路,首先，容易列举出N=1,2,3的情况： 0 0，1 0，2，3,2020/9/7,10,先来看个统计的方法： 假设一共有n=a+b条直线 （即n条直线分成2组，分别为a条和b条） 则总的交点数= a内的交点数 b内的交点数 a，b之间的交点数,重点分析n的情况：,2020/9/7,11,我们来分析加入第N条直线的情况(这里以N=4为例)： （分类方法：和第N条直线平行的在a组，其余在b组） 1、第四条与其余直线全部平行 = 0+4*0+0=0； 2、第四条与其中两条平行，交点数为0+(n-1)*1+0=3; 3、第四条与其中一条平行，这两条平行直线和另外两点直线的交点数为(n-2)*2=4,而另外两条直线既可能平行也可能相交，因此可能交点数为： 0+（n-2）*2+0=4 或者 0+(n-2)*2+1=5 4、 第四条直线不与任何一条直线平行，交点数为： 0+(n-3)*3+0=3 或0+ (n-3)*3+2=5 或0+ (n-3)*3+3=6 即n=4时，有0个，3个，4个，5个，6个不同交点数。
重点分析n的情况：,2020/9/7,12,从上述n=4的分析过程中，我们发现： m条直线的交点方案数 =（m-r）条平行线与r条直线交叉的交点数 + r条直线本身的交点方案 =（m-r）*r+r条之间本身的交点方案数（0<=r
所以实际求解时，可从底层开始，层层递进，最后得到最大值 结论：自顶向下的分析，自底向上的计算考虑一下：,2020/9/7,18,二、思考题：最长有序子序列,2020/9/7,19,解决方案：,2020/9/7,20,,,三、1160 FatMouses Speed,Sample Input 6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900,Sample Output4 4 5 9 7,2020/9/7,21,题目分析：,设Micei.W表示第i只老鼠的重量，Micei.S表示第i只老鼠的速度我们先对Mice进行排序，以W为第一关键字，从小到大，S为第二关键字，从大到小 设fi为Micei至Micen最长的序列长度考虑某一个fi，则有： fi = max(fi, fj+1) (1 Micej.W，Micei.S < Micej.S) 其中，初始条件为fi=1 (i=1, 2, ..., n)2020/9/7,22,Qestion:,两个问题有本质区别吗？,2020/9/7,23,思考（期末考试题）：,Super Jumping! Jumping!Juping!,解题思路？,2020/9/7,25,,,四、1159 Common Subsequence,Sample Inputabcfbc abfcabprogramming contest abcd mnp,Sample Output 4 2 0,2020/9/7,26,辅助空间变化示意图,2020/9/7,27,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),子结构特征：,2020/9/7,28,思考：免费馅饼,2020/9/7,29,如何解决？,请发表见解 ,Any question?,2020/9/7,31,理论小结,2020/9/7,32,如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。
由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中一、动态规划的基本思想,2020/9/7,33,二、动态规划的基本步骤,动态规划算法通常用于求解具有某种最优性质的问题在这类问题中，可能会有许多可行解每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解设计一个动态规划算法，通常可以按以下几个步骤进行：,2020/9/7,34,（1）找出最优解的性质，并刻画其结构特征 （2）递归地定义最优值 （3）以自底向上的方式计算出最优值 （4）根据计算最优值时得到的信息，构造一个最优解 其中（1）（3）步是动态规划算法的基本步骤在只需要求出最优值的情形，步骤（4）可以省去若需要求出问题的一个最优解，则必须执行步骤（4）此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出一个最优解基本步骤,2020/9/7,35,三、动态规划问题的特征,动态规划算法的有效性依赖于问题本身所具有的两个重要性质： 1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解2020/9/7,36,课后任务：,一、DIY作业(4): ACM程序设计作业（4） 动态规划（第一部分） 二、常规练习（包含以上作业） 1003、1466 、 1087、1176、 2084、1159、1160 1058、1069、2059、2151,2020/9/7,37,下一讲：,计算几何,2020/9/7,38,Welcome to HDOJ,Thank You ,。