acm动态规划入门
今天，
你 了吗？
AC
acm动态规划入门
2021/5/7
2
每周一星（3）：
Lomen
acm动态规划入门
2021/5/7
3
第四讲
动态规划(1)
（Dynamic programming）
acm动态规划入门
2021/5/7
4
先热身一下——
acm动态规划入门
2021/5/7
5
(1466)计算直线的交点数
问题描述：
平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
输入：n（n<=20）
输出：每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数。
样例输入
4
样例输出
0 3 4 5 6
acm动态规划入门
2021/5/7
6
初步分析:
我们知道:
n条直线互不平行且无三线共点的最多交点数max=1+2+……(n-1)=n(n-1)/2,
但本题不这么简单，因为问题问的是：这些直线有多少种不同的交点数？
acm动态规划入门
2021/5/7
7
思考2分钟:如何解决?
acm动态规划入门
2021/5/7
8
然后，假设<=n-1的情况都已经知道——
分析思路——
首先，容易列举出N=1,2,3的情况：
0
0，1
0，2，3
acm动态规划入门
2021/5/7
9
先来看个统计的方法：
假设一共有n=a+b条直线
（即n条直线分成2组，分别为a条和b条）
则总的交点数= a内的交点数
＋b内的交点数
＋a，b之间的交点数
重点分析——n的情况：
acm动态规划入门
2021/5/7
10
acm动态规划入门 来自淘豆网m.daumloan.com转载请标明出处.
