1174: 计算直线的交点数

解题思路:

注意事项:

参考代码:

#include<iostream>

using namespace std;

int main()

{

int n;

while (cin >> n)

{

int dp[21][200] = { 0 };

for (int i = 0; i < 21; i++)// i 表示有几条线，j 表示交点个数，1 表示 i 条线存在 j 个交点

{

dp[i][0] = 1;//都平行，就存在 0 个交点

}

for (int n = 2; n < 21; n++)//n 表示的是当前总共的线

{

for (int i = 1; i < n; i++)// i 表示 n 条线中有几条线平行

{

for (int j = 0; j < 200; j++)// j 的意义同上面的 j 

{

if (dp[n - i][j] == 1)// 如果除去平行的线，在 j 交点处有意义，则加上平行后的交点也有了意义

{

dp[n][j + i * (n - i)] = 1;// i * (n-i) 就是不平行线 乘以 平行线 数量，这很好理解

}

}

}

}

for (int j = 0; j < 200; j++)//题目给的是 线数 ， 我们要输出的是 可能的交点数

{

if (dp[n][j] == 1)

{

cout << j << " ";

}

}

cout << endl;

}

return 0;

}