acm动态规划入门刘春英课件.ppt
《acm动态规划入门刘春英课件.ppt》由会员分享,可在线阅读,更多相关《acm动态规划入门刘春英课件.ppt(38页珍藏版)》请在三一文库上搜索。
1、ACM程序设计,杭州电子科技大学 刘春英 ,2019/3/3,2,今天,,你 了吗?,AC,2019/3/3,3,每周一星(3):,Lomen,2019/3/3,4,第四讲,动态规划(1) (Dynamic programming),2019/3/3,5,先热身一下,2019/3/3,6,(1466)计算直线的交点数,问题描述: 平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。 输入:n(n=20) 输出:每个测试实例对应一行输出,从小到大列出所有相交方案,其中每个数为可能的交点数。 样例输入 4 样例输出 0 3 4 5 6,2019/3/3,7,初步分析:,我们知道: n条
2、直线互不平行且无三线共点的最多交点数max=1+2+(n-1)=n(n-1)/2, 但本题不这么简单,因为问题问的是:这些直线有多少种不同的交点数?,2019/3/3,8,思考2分钟:如何解决?,2019/3/3,9,然后,假设=n-1的情况都已经知道,分析思路,首先,容易列举出N=1,2,3的情况: 0 0,1 0,2,3,2019/3/3,10,先来看个统计的方法: 假设一共有n=a+b条直线 (即n条直线分成2组,分别为a条和b条) 则总的交点数= a内的交点数 b内的交点数 a,b之间的交点数,重点分析n的情况:,2019/3/3,11,我们来分析加入第N条直线的情况(这里以N=4为例
3、): (分类方法:和第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的情况:,2
4、019/3/3,12,从上述n=4的分析过程中,我们发现: m条直线的交点方案数 =(m-r)条平行线与r条直线交叉的交点数 + r条直线本身的交点方案 =(m-r)*r+r条之间本身的交点方案数(0=rm),重点分析n的情况:,2019/3/3,13,一、数塔问题,有形如下图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的值最大。,2019/3/3,14,用暴力的方法,可以吗?,2019/3/3,15,这道题如果用枚举法(暴力思想),在数塔层数稍大的情况下(如31),则需要列举出的路径条数将是一个非常庞大的数目(230= 10243 10
5、9=10亿)。,试想一下:,2019/3/3,16,拒绝暴力,倡导和谐,2019/3/3,17,从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值,只要左右两道路径上的最大值求出来了才能作出决策。 同样,下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去,直到倒数第二层时就非常明了。 如数字2,只要选择它下面较大值的结点19前进就可以了。所以实际求解时,可从底层开始,层层递进,最后得到最大值。 结论:自顶向下的分析,自底向上的计算。,考虑一下:,2019/3/3,18,二、思考题:最长有序子序列,2019/3/3,19,解决方案:,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- acm 动态 规划 入门 刘春英 课件
链接地址:https://www.31doc.com/p-2200943.html