[hdu] P1466 计算直线的交点数

题目链接
组合数学题，考虑递推

如果要求n条直线中任意两条直线都有交点，设$a_n$为n条直线产生的交点数，那么易得 $a_n=a_{n-1}+n-1$ 因为把第n条直线加入到前n-1条直线的平面时，会与这n-1条直线都构成一个交点。
现在去掉“两两相交”条件，那么在加入第n条直线的时候就有直线与之平行，对交点数没有贡献。这启示我们从平行直线这个角度考虑问题。设$f(i,j)$为有i条直线构成j个交点是否可行，前i-1条直线有k条与其平行，$f(i,j)=1$当且仅当$f(i-1-k,j-(k+1)(i-1-k))=1$时成立。

完整代码：

#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn = 1e5+5;

using namespace std;

int n;
int dp[1001][1001];

int main()
{
    
   	FAST; 
   	for (int i=1; i<=20; i++) dp[i][0]=1;
   	for (int i=2; i<=20; i++)
	{
    
		for (int j=1; j<=200; j++)
			for (int k=0; k<=i-1; k++)
				if (dp[i-1-k][j-(k+1)*(i-1-k)]) dp[i][j]=1;	
	}
	
   	while(cin>>n)
   	{
    
		for (int i=0; i<=n*(n-1)/2-1; i++)
			if (dp[n][i]) cout<<i<<' ';
			cout<<n*(n-1)/2<<endl;
	}
	
return 0;
}