hdu 1466 计算直线的交点数

http://acm.hdu.edu.cn/showproblem.php?pid=1466

N条直线的交点方案数 = c 条直线交叉的交点数与(N-c)条平行线 + c 条直线本身的交点方案 = (N - c) * c + c 条直线之间的交点数。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int dp[21][200];
 7 
 8 void inti()
 9 {
10     for(int i=0; i<=20; i++)
11     {
12         for(int j=0; j<=190; j++)
13             dp[i][j]=0;
14     }
15     for(int i=0; i<=20; i++)
16     {
17         dp[i][0]=1;
18         for(int j=0; j<=i; j++)
19         {
20             for(int k=0; k<=j*(j-1)/2; k++)
21             {
22                 dp[i][(i-j)*j+dp[j][k]*k]=1;
23             }
24         }
25     }
26 }
27 
28 int main()
29 {
30     int n;
31     inti();
32     while(scanf("%d",&n)!=EOF)
33     {
34         printf("0");
35         for(int i=1; i<=190; i++)
36         {
37             if(dp[n][i])
38             {
39                 printf(" %d",i);
40             }
41         }
42         printf("
");
43     }
44     return 0;
45 }

View Code