hdu1466 计算直线的交点数

题意：

平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。

比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。

分析：

DP

设状态：f[i][j]表示i条直线能否产生j个交点。

有不同的交点数--->n条直线中有平行线。；n个点最多有n(n-1)/2个交点。

i条直线中j(j<=i)条平行线，i-j条自由线。

则此种交法的交点数就为(i-j)*j+k((i-j)*j为i-j条自由线与j条平行线的交点数，k为i-j条自由线的交点数  )

则状态转移方程：f[i][j] = f[(i-j)*j+k]( f[i-j][k]为真 )

code:

 

#include <stdio.h> #include <string.h> const int maxn = 21; int f[maxn][191]; void init() {int i, j, k;memset(f,0,sizeof(f));for(i=1; i<maxn; i++)f[i][0] = 1;for(i=1; i<maxn; i++)for(j=0; j<i; j++)for(k=0; k<=(i-j)*(i-j-1)/2; k++)if(f[i-j][k])f[i][(i-j)*j+k] = 1; } int main() {int n, i;init();while(~scanf("%d",&n)){printf("0");for(i=1; i<=n*(n-1)/2; i++)if(f[n][i])printf(" %d",i);printf("\n");}return 0; }

 

 

总结

以上是生活随笔为你收集整理的hdu1466 计算直线的交点数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。