[hdu] p1466 calculate the number of intersections of straight lines

Topic link
Combinatorial problems , Consider recursion

If requirement n Any two of these lines have intersections , set up $a_n$ by n The number of intersections generated by the lines , So easy to get $a_n=a_{n-1}+n-1$ Because the second n A line is added to the front n-1 The plane of a straight line , Will be with this n-1 All the lines form an intersection .
Now get rid of “ Two intersect ” Conditions , that In joining the n When there is a straight line, there is a straight line parallel to it , No contribution to intersection points . This tells us Consider the problem from the perspective of parallel lines . set up $f(i,j)$ To have i A straight line forms j Is the intersection feasible , front i-1 This straight line has k The bar is parallel to it ,$f(i,j)=1$ If and only if $f(i-1-k,j-(k+1)(i-1-k))=1$ It was established .

Complete code ：

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