ACM算法 动态规划(1)
40页1、2018/9/8,1,ACM 程序设计,计算机学院 刘春英,2018/9/8,2,今天,,你 了吗?,AC,2018/9/8,3,每周一星(3):,liuzewei,2018/9/8,4,第四讲,动态规划(1) (Dynamic programming),2018/9/8,5,先热身一下,2018/9/8,6,(1466)计算直线的交点数,问题描述:平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。 输入:n(n=20) 输出:每个测试实例对应一行输出,从小到大列出所有相交方案,其中每个数为可能的交点数。 样例输入 4 样例输出 0 3 4 5 6,2018/9/8,7,思考2分钟:如何解决?,2018/9/8,8,初步分析:,我们将n条直线排成一个序列, 直线2和直线1最多只有一个交点, 直线3与直线1和直线2最多有两个交点., 直线n和其他n-1条直线最多有n-1个交点, 由此得出n条直线互不平行且无三线共点的最多交点数max=1+2+(n-1)=n(n-1)/2,但本题不这么简单,因为问题问的是:这些直线有多少种不同的交点数?,2018/9/8,9,容易列举出N=1
2、,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个不同交点数。,2018/9/8,10,从上述n=4的分析过程中,我们发现:m条直线的交点方案数=(m-r)条平行线与r条直线交叉的交点数+ r条直线本身的交点方案=(m-r)*r+r条之间本身的交点方案数(1=r 109=10亿)。,2018/9/8,14,所以,不可以如此暴力!,2018/9/8,15,考虑一下:从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值,只要左右两道路径上的最大值求出来了才能作出决策。同样,下一层的走向又要取决于再下一层上的最大值是否已经求出才能决
3、策。这样一层一层推下去,直到倒数第二层时就非常明了。如数字2,只要选择它下面较大值的结点19前进就可以了。所以实际求解时,可从底层开始,层层递进,最后得到最大值。结论:自顶向下的分析,自底向上的计算。,2018/9/8,16,Understand?,2018/9/8,17,二、思考题:最长有序子序列,请回答: 穷举(暴力)方法的时间复杂度是多少?,2018/9/8,18,解决方案:,2018/9/8,19,三、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,2018/9/8,20,题目分析:,设Micei.W表示第i只老鼠的重量,Micei.S表示第i只老鼠的速度。我们先对Mice进行排序,以W为第一关键字,从小到大,S为第二关键字,从大到小。 设fi为Micei至Micen最长的序列长度。考虑某一个fi,则有: fi =
《ACM算法 动态规划(1)》由会员飞***分享,可在线阅读,更多相关《ACM算法 动态规划(1)》请在金锄头文库上搜索。
人教版一年级下册数学第二单元20以内的退位减法测试卷精品【考试直接用】
人教版一年级下册数学第二单元20以内的退位减法测试卷(实用)word版
人教版一年级下册数学第二单元20以内的退位减法测试卷及答案(夺冠)
人教版一年级下册数学第二单元20以内的退位减法测试卷(典型题)
人教版一年级下册数学第二单元20以内的退位减法测试卷精品(a卷)
人教版一年级下册数学第二单元20以内的退位减法测试卷及答案【精品】
部编版二年级上册道德与法治期中测试卷 (考试直接用)
部编版二年级上册道德与法治期中测试卷 带答案(培优)
部编版二年级上册道德与法治期中测试卷 含答案(精练)
部编版二年级上册道德与法治期中测试卷 及答案【各地真题】
部编版二年级上册道德与法治期中测试卷 及完整答案【名校卷 】
部编版二年级上册道德与法治期中测试卷 【考点精练】
部编版三年级上册道德与法治期末测试卷 (重点)
部编版三年级上册道德与法治期末测试卷 (模拟题)word版
部编版三年级上册道德与法治期末测试卷 附答案(预热题)
部编版三年级上册道德与法治期末测试卷 附参考答案(b卷 )
部编版三年级上册道德与法治期末测试卷 答案下载
部编版三年级上册道德与法治期末测试卷 含答案【夺分金卷 】
部编版三年级上册道德与法治期末测试卷 含完整答案【网校专用】
部编版三年级上册道德与法治期末测试卷 及答案(最新)
2024-04-08 20页
2024-04-06 36页
2024-02-09 36页
2024-01-31 31页
2024-01-28 18页
2024-01-28 31页
2024-01-28 24页
2024-01-28 27页
2024-01-28 24页
2024-01-28 25页