首页 > 代码库 > hdu 1466 计算直线的交点数

hdu 1466 计算直线的交点数

2024-07-13 19:35:00   222人阅读

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("\n");43     }44     return 0;45 }
View Code


联系
我们