《acm动态规划入门刘春英.ppt》由会员分享，可在线阅读，更多相关《acm动态规划入门刘春英.ppt（38页珍藏版）》请在金锄头文库上搜索。
1、ACM程序设计程序设计杭州电子科技大学 刘春英7/25/20241今天，今天，你你 了吗？了吗？AC7/25/20242每周一星（每周一星（3）：）：Lomen 7/25/20243第四讲第四讲动态规划动态规划(1)(1) （Dynamic programmingDynamic programming）7/25/20244先热身一下先热身一下7/25/20245(1466)计算直线的交点数计算直线的交点数问题描述： 平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。输入：n（n=20）输出：每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数。样例输入4样
2、例输出0 3 4 5 67/25/20246初步分析初步分析:我们知道我们知道: : n n条直线互不平行且无三线共点的最多条直线互不平行且无三线共点的最多交点数交点数max=1+2+(n-1)=n(n-1)/2,max=1+2+(n-1)=n(n-1)/2,但本题不这么简单，因为问题问的是：但本题不这么简单，因为问题问的是：这些直线有这些直线有多少种多少种不同的交点数？不同的交点数？7/25/20247思考思考2分钟分钟:如何解决如何解决?7/25/20248然后，然后，假设假设=n-1 0+4*0+0=0= 0+4*0+0=0；2 2、第四条与其中两条平行，交点数为、第四条与其中两条平行，
3、交点数为0+(n-1)*1+0=3;0+(n-1)*1+0=3;3 3、第四条与其中一条平行，这两条平行直线和另外两点直线的交、第四条与其中一条平行，这两条平行直线和另外两点直线的交点数为点数为(n-2)*2=4,(n-2)*2=4,而另外两条直线既可能平行也可能相交，因此而另外两条直线既可能平行也可能相交，因此可能交点数为：可能交点数为： 0+0+（n-2n-2）* *2+0=42+0=4 或者或者 0+(0+(n-2n-2)*2+1=5)*2+1=5 4 4、 第四条直线不与任何一条直线平行，交点数为：第四条直线不与任何一条直线平行，交点数为： 0+(n-3)*3+0=3 0+(n-3)*
4、3+0=3 或或0+0+ (n-3)*3+2=5 (n-3)*3+2=5 或或0+0+ (n-3)*3+3=6(n-3)*3+3=6即即n=4n=4时，有时，有0 0个，个，3 3个，个，4 4个，个，5 5个，个，6 6个不同交点数。个不同交点数。重点分析重点分析n的情况：的情况：7/25/202411从上述从上述n=4n=4的分析过程中，我们发现：的分析过程中，我们发现：m m条直线的交点方案数条直线的交点方案数= =（m-rm-r）条平行线与）条平行线与r r条直线交叉的交点数条直线交叉的交点数 + r+ r条直线本身的交点方案条直线本身的交点方案= =（m-rm-r）* *r+rr+r
5、条之间本身的交点方案数条之间本身的交点方案数（0=rm0=r 109=10亿）。试想一下：试想一下：7/25/202415 拒绝拒绝暴力，暴力，倡导倡导和谐和谐7/25/202416从顶点出发时到底向左走还是向右走应取决于是从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走向又要取决于再下一层上的最同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，大值是否已经求出才能决策
6、。这样一层一层推下去，直到倒数第二层时就非常明了。直到倒数第二层时就非常明了。如数字如数字2，只要选择它下面较大值的结点，只要选择它下面较大值的结点19前进就前进就可以了。所以实际求解时，可从底层开始，层层递进，可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。最后得到最大值。结论：自顶向下的分析，自底向上的计算。结论：自顶向下的分析，自底向上的计算。考虑一下：考虑一下：7/25/202417二、思考题：最长有序子序列二、思考题：最长有序子序列I012345678NumI1472583697/25/202418解决方案：解决方案：I012345678NumI147258369FI
7、1232343457/25/202419三、三、1160 FatMouses Speed nSample Input6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900 Sample Output4 4 5 9 77/25/202420题目分析：题目分析：n设Micei.W表示第i只老鼠的重量，Micei.S表示第i只老鼠的速度。我们先对Mice进行排序，以W为第一关键字，从小到大，S为第二关键字，从大到小。n设fi为Micei至Micen最长的序列长度。考虑某一个fi，
8、则有： nfi = max(fi, fj+1) (1=j Micej.W，Micei.S Micej.S) n其中，初始条件为fi=1 (i=1, 2, ., n)。7/25/202421Qestion:两个问题有本质两个问题有本质区别吗？区别吗？7/25/202422思考（期末考试题）：思考（期末考试题）：Super Jumping! Jumping!Jumping! 7/25/202423解题思路？解题思路？7/25/202424四、四、1159 Common SubsequenceSample Inputabcfbc abfcabprogramming contest abcd mnp
9、Sample Output 4 2 07/25/202425abcfbca111111b122222f122333c123334a123334b123344辅助空间变化示意图辅助空间变化示意图7/25/202426f(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(len(a),len(b)就得到所要求的解了.f(i-1,j-1)+1 (ai=bj)max(f(i-1,j),f(i,j-1) (ai!=bj)
10、 子结构特征：子结构特征：7/25/202427理论小结理论小结7/25/202428如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。 一、动态规划的基本思想一、动态规划的基本思想 7/25/202429二、动态规划的基本步骤二、动态规划的基本步骤 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希
11、望找到具有最优值（最大值或最小值）的那个解。设计一个动态规划算法，通常可以按以下几个步骤进行： 7/25/202430（1）找出最优解的性质，并刻画其结构特征。）找出最优解的性质，并刻画其结构特征。（2）递归地定义最优值。）递归地定义最优值。（3）以）以自底向上自底向上的方式计算出最优值。的方式计算出最优值。（4）根据计算最优值时得到的信息，构造一个最优解。）根据计算最优值时得到的信息，构造一个最优解。其中（其中（1）（）（3）步是动态规划算法的基本步骤。在只）步是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（需要求出最优值的情形，步骤（4）可以省去。若需要）可以省去。若需要求出问题
12、的一个最优解，则必须执行步骤（求出问题的一个最优解，则必须执行步骤（4）。此时，）。此时，在步骤（在步骤（3）中计算最优值时，通常需记录更多的信息，）中计算最优值时，通常需记录更多的信息，以便在步骤（以便在步骤（4）中，根据所记录的信息，快速构造出）中，根据所记录的信息，快速构造出一个最优解。一个最优解。基本步骤基本步骤 7/25/202431三、动态规划问题的特征三、动态规划问题的特征 动态规划算法的有效性依赖于问题本身所具有的两个重要性质：1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总
13、是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。7/25/202432思考：思考：免费馅饼免费馅饼 7/25/202433如何解决？如何解决？请发表见解请发表见解 7/25/202434Any question?7/25/202435课后任务：课后任务：一、一、DIYDIY在线作业在线作业(4):(4):20082008ACM ProgrammingACM ProgrammingExerciseExercise（4 4）_ _动态规划动态规划二、常规练习（包含以上作业）二、常规练习（包含以上作业）n10031003、1466 1466 、n10871087、11591159、n11761176、10581058、n10691069、20592059、n20842084、215121517/25/202436下一讲：下一讲：计算几何计算几何7/25/202437Welcome to HDOJThank You 7/25/202438
