跳到主要内容
原文210 词数1 分钟

题解：P2789 直线交点数

概述

平面上有 n 条直线且无三线共点，求可能出现的交点数有多少种。把同组平行线视为损失若干交点，转化为完全背包：状态记录形成某个交点损失量所需的最少直线数，枚举平行线组大小作为物品。最后统计用不超过 n 条直线可以达到的损失量个数。时间复杂度为 O(n^3)。

参考资料​

题意简述​

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

解题思路​

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

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

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

参考代码​

408 Bcpp
#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;
}