题解：P2789 直线交点数

lailai0916 · 2026-01-06 00:16:50 · 题解

参考资料

• A069999 - OEIS

题意简述

平面上有 n 条直线，且无三线共点，求这些直线有多少种可能的交点数。

解题思路

此问题可以转化为 完全背包 问题：

• 状态定义：f_i 表示损失 i 个交点消耗直线数量的最小值；
• 背包容量：最大交点损失数量 m=\frac{n(n-1)}{2}；
• 物品类型：平行线组数量 j\in[2,n]；
• 物品价值：消耗直线数量 j；
• 物品体积：交点损失数量 w=\frac{j(j-1)}{2}；
• 状态转移：f_i=\min(f_i,f_{i-w}+j)。

时间复杂度为 O(n^3)。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int N=1005;
int f[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    int m=n*(n-1)/2;
    for(int i=1;i<=m;i++)f[i]=inf;
    for(int j=2;j<=n;j++)
    {
        int w=j*(j-1)/2;
        for(int i=w;i<=m;i++)f[i]=min(f[i],f[i-w]+j);
    }
    int ans=0;
    for(int i=0;i<=m;i++)if(f[i]<=n)ans++;
    cout<<ans<<'\n';
    return 0;
}