动态规划解决问题

解题思路:

核心思想：将直线分成若干平行组，每个平行组大小为 p≥2p≥2，该组内部减少 (p2)(2p) 个交点。

动态规划：dp[s][loss]：用 s 条直线组成平行组，能否减少 loss 个交点

完全背包方式，每个组大小可以选多次

结果收集：所有可能的交点 = 最大交点数 - 减少的交点数

没有被分到平行组中的直线作为单独组，不减少交点

注意事项:

参考代码:

#include <stdio.h>

#include <string.h>

#include <stdbool.h>

#define MAX_N 100

#define MAX_K 5000  // C(100,2) = 4950

/**

 * 求解n条直线所有可能的交点数

 * 原理：将直线分成若干平行组，每组大小 p_i >= 2

 * 总交点数 = C(n,2) - sum(C(p_i,2))

 */

void solve(int n) {

    int max_k = n * (n - 1) / 2;  // 最大交点数

    // dp[s][loss] 表示用 s 条直线组成若干平行组，

    // 能否减少 loss 个交点

    static bool dp[MAX_N + 1][MAX_K + 1];

    memset(dp, 0, sizeof(dp));

    dp[0][0] = true;  // 0条直线，减少0个交点

    // 枚举平行组大小 p (p >= 2)

    // 使用完全背包，每种大小可以选任意多个

    for (int p = 2; p <= n; p++) {

        int loss = p * (p - 1) / 2;  // C(p,2)

        // 完全背包：正序循环，允许重复选择同一大小

        for (int s = p; s <= n; s++) {

            for (int k = 0; k + loss <= max_k; k++) {

                if (dp[s - p][k]) {

                    dp[s][k + loss] = true;

                }

            }

        }

    }

    // 收集所有可能的交点数

    bool result[MAX_K + 1] = {false};

    for (int s = 0; s <= n; s++) {

        for (int loss = 0; loss <= max_k; loss++) {

            if (dp[s][loss]) {

                // 剩余 n-s 条直线不属于任何平行组（即单独一组）

                // 它们不减少交点，所以交点数 = max_k - loss

                result[max_k - loss] = true;

            }

        }

    }

    // 输出结果（升序）

    bool first = true;

    for (int k = 0; k <= max_k; k++) {

        if (result[k]) {

            if (!first) printf(" ");

            printf("%d", k);

            first = false;

        }

    }

    printf("\n");

}

int main() {

    int n;

    // 读取多组数据，每行一个n

    // 输入 Ctrl+Z (Windows) 或 Ctrl+D (Linux) 结束

    while (scanf("%d", &n) == 1) {

        if (n <= 0) {

            // 如果n<=0，没有交点，直接输出0

            printf("0\n");

            continue;

        }

        solve(n);

    }

    return 0;

}