题目描述

平面上有 n 条直线，且无三线共点，问这些直线能有多少种不同交点数。
比如，如果 n = 2，则可能的交点数量为 0（平行）或者 1（不平行）。
输入数据包含多个测试实例，每个测试实例占一行，每行包含一个正整数 n（n <= 20），n表示直线的数量。
每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数，每行的整数之间用一个空格隔开。
样例输入：
2
3
样例输出：
0 1
0 2 3
http://acm.hdu.edu.cn/showproblem.php?pid=1466

题解

动态规划

n 条直线时，如果全平行，交点数为 0，这种情况相当于我们将 n 条直线拆分成 0 和 n 条平行线。

同样的，我们还可以将 n 条直线拆分成 1 和 n - 1 条平行线，交点数为 n - 1 。

继续拆分出更多的相交直线，直到任意两条直线都相交。

可以发现如果我们将 n 条直线拆分成 j 和 n - j 条平行线，我们又需要讨论 j 条线中有几条平行线，然后对每种情况，分别与 n - j 条平行线相交。

假设 j 条线都是平行线（但是与另外 n - j 条平行线是不平行的），那么交点数为 j * (n - j) + 0

假设 j 条线有 j - 1 条平行线，那么交点数为 j * (n - j) + j - 1

。。。

其实无论 j 条线的情况如何，j 条线都至少有 j * (n - j) 个交点数，这是 j 条线与 n - j 条平行线的交点，与 j 的情况无关。

然后再加上 j 条线的交点数的各种情况，也就是当我们拆分 n = j + (n - j) 时的所有交点数的可能情况了。

综上，对 n 条线，我们就拆分 n = j + (n - j)，这样遍历 j 的所有可能取值，对每个 j 遍历 ans[j] 的情况，就得到了 ans[n] 的结果了。

同时我们用 set 实现去重并自动排序。

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
    vector<set<int>> ans(21);           // n <= 20
    for (int i = 0; i < 21; i++) {
        ans[i].insert(0);
        for (int j = 1; j < i; j++) {	// i = j + (i - j)
            int t = (i - j) * j;
            for (int k : ans[j]) {
                ans[i].insert(t + k);
            }
        }
    }
    int n;
    while (cin >> n) {
        for (int i : ans[n]) cout << i << " ";
        cout << endl;
    }
    return 0;
}