G 문제 hdu 1466 계산 직선 의 교점 수

제목 링크: http://acm.hdu.edu.cn/showproblem.php?pid=1466
직선 의 교점 수 를 계산 하 다
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 8799    Accepted Submission(s): 3973
Problem Description
평면 에 n 개의 직선 이 있 고 3 선의 공통점 이 없 으 며 이 직선 들 이 몇 가지 서로 다른 교점 이 있 는 지 물 어보 세 요.
예 를 들 어 n = 2 이면 가능 한 교점 수량 은 0 (평행) 또는 1 (평행 하지 않 음) 이다.
 
 
Input
입력 데 이 터 는 여러 개의 테스트 인 스 턴 스 를 포함 하고 모든 테스트 인 스 턴 스 는 한 줄 을 차지 하 며 각 줄 은 하나의 정수 n (n < 20) 을 포함 하고 n 은 직선 수량 을 표시 합 니 다.
 
 
Output
모든 테스트 인 스 턴 스 는 한 줄 의 출력 에 대응 하고 작은 것 부터 큰 것 까지 모든 교차 방안 을 보 여 줍 니 다. 그 중에서 모든 수 는 가능 한 교차 포인트 이 고 모든 줄 의 정수 사 이 를 빈 칸 으로 구분 합 니 다.
 
 
Sample Input
2
3
 
 
Sample Output
0 1
0 2 3
 
Author
lcy
 
 
Source
ACM 여름 캠프 연습 경기 (9)
 
제목 의 대의: 직선 적 인 교점 수 를 계산 하고 평행 문 제 를 고려 하여 마지막 으로 가능 한 교점 개 수 를 출력 합 니 다.
 
문제 풀이 방향: 여기 dp 방법 을 사용 합 니 다.코드 에 상세 한 설명 이 있 습 니 다.
 
코드 참조.

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstring>

 4 

 5 using namespace std;

 6 

 7 long long a[21][200]; //a[i][j]  i    j   ，  20      C（20,2）=190   

 8                       // 200    ，        。

 9 

10 int main ()

11 {

12     memset(a, 0, sizeof(0));

13     for (int i=1; i<=20; i++)

14     {

15         a[i][0] = 1;

16         for (int j=1; j<=i; j++)        //i     j     ，  i-j     。

17         {

18             for (int k=0; k<=190; k++)  //  0-190， j   k     ，    i-j      i  (i-j)*j+k     

19             {

20                 if (a[j][k])

21                 a[i][(i-j)*j+k] = 1;

22             }

23         }

24     }

25     int n;

26     while (scanf ("%d",&n)==1)

27     {

28         printf ("0");

29         for (int i=1; i<=190; i++)

30         if (a[n][i])

31         printf (" %d",i);

32         printf ("
");

33     }

34     return 0;

35 }