P2789 直线交点数

参考资料

• 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;
}