lecture动态规划.ppt

文档介绍：ACM 程序设计
计算机学院刘春英
4/27/2018
1
今天,
你了吗?
AC
4/27/2018
2
每周一星(3):
liuzewei
4/27/2018
3
第四讲
动态规划(1) (Dynamic programming)
4/27/2018
4
先热身一下——
4/27/2018
5
(1466)计算直线的交点数
问题描述:
平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。
输入:n(n<=20)
输出:每个测试实例对应一行输出,从小到大列出所有相交方案,其中每个数为可能的交点数。
样例输入
4
样例输出
0 3 4 5 6
4/27/2018
6
思考2分钟:如何解决?
4/27/2018
7
初步分析:
我们将n条直线排成一个序列,
直线2和直线1最多只有一个交点,
直线3与直线1和直线2最多有两个交点…….,
直线n和其他n-1条直线最多有n-1个交点,
由此得出n条直线互不平行且无三线共点的最多交点数max=1+2+……(n-1)=n(n-1)/2,
但本题不这么简单,因为问题问的是:这些直线有多少种不同的交点数?
4/27/2018
8
容易列举出N=1,2,3的情况:
0
0,1
0,2,3
如果已知<N的情况,我们来分析加入第N条直线的情况(这里N=4):
1、第四条与其余直线全部平行=> 无交点;
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个不同交点数。
4/27/2018
9
从上述n=4的分析过程中,我们发现:
m条直线的交点方案数
=(m-r)条平行线与r条直线交叉的交点数
+ r条直线本身的交点方案
=(m-r)*r+r条之间本身的交点方案数(1<=r<=m)
4/27/2018
10