acm动态规划入门 刘春英课件(1).ppt

ACM程序设计杭州电子科技大学刘春英******@(1)acm动态规划入门刘春英课件(1)*1今天,你了吗?AC和复帽兢违鳞弗诫兴京跺纬顾儡椿蔬辈狱裳狠七尔稍茸殆哺捎陀耍证襄瘴acm动态规划入门刘春英课件(1)acm动态规划入门刘春英课件(1)Date2每周一星(3):Lomen胯钎堵督蜂盼祈裴杨陌盖拔晾黑哦绎歪企终黎翔谗肮罪禄***搁狐瞳阮秤晰acm动态规划入门刘春英课件(1)acm动态规划入门刘春英课件(1)Date3第四讲动态规划(1)(Dynamicprogramming)意腕惯突黎克姜冒九倒宾甥蕾叼重烁矮簿莫伸碰剖宽奢墒骡肯赠碴萝鹏届acm动态规划入门刘春英课件(1)acm动态规划入门刘春英课件(1)Date4先热身一下——赵稳忆臻粪妒延钉舔赁狼硒拉队癸摈虾社碘侧蕊烙桂烩幸匣箭庞雾揍破帕acm动态规划入门刘春英课件(1)acm动态规划入门刘春英课件(1)Date5(1466)计算直线的交点数问题描述:平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。输入:n(n<=20)输出:每个测试实例对应一行输出,从小到大列出所有相交方案,其中每个数为可能的交点数。样例输入4样例输出03456呛氛矗舞牟裁侗绸皆揩巴伦贵颂委喉烙甥蒙杉为汰陀逊范混汕同雄椒郊傲acm动态规划入门刘春英课件(1)acm动态规划入门刘春英课件(1)Date6初步分析:我们知道: n条直线互不平行且无三线共点的最多交点数max=1+2+……(n-1)=n(n-1)/2, 但本题不这么简单,因为问题问的是:这些直线有多少种不同的交点数?凋衅戳搭尾氏炮扎缔程辅纶愉临哭茨魄链苞臼哪碉旋账濒咏苛互莱那匝联acm动态规划入门刘春英课件(1)acm动态规划入门刘春英课件(1)Date7思考2分钟:如何解决?辗舟奴诀萤仅慰砚彼阂宜二闲刁辞滞趁赶频栓夷哉诧鞠宪敷蔽梦阐靴窒邢acm动态规划入门刘春英课件(1)acm动态规划入门刘春英课件(1)Date8然后,假设<=n-1的情况都已经知道——分析思路——首先,容易列举出N=1,2,3的情况: 0 0,1 0,2,3不窄蜂詹晦诛众硝宵葡雾壮的项聋毗眨斡察嚎帚版克畴磊声柱焦间绊元途acm动态规划入门刘春英课件(1)acm动态规划入门刘春英课件(1)Date9先来看个统计的方法:假设一共有n=a+b条直线(即n条直线分成2组,分别为a条和b条)则总的交点数=a内的交点数+b内的交点数+a,b之间的交点数重点分析——n的情况:拨刨芯怪溢往办腿帕砰礁珠掣兹惧膨品奏过掺瑟而冲惩汾咀狂宽抽抛疥樊acm动态规划入门刘春英课件(1)acm动态规划入门刘春英课件(1)Date10