首页 > 代码库 > hdu 1466 计算直线的交点数 递推
hdu 1466 计算直线的交点数 递推
以前做这道题目的时候，花了好长时间找规律，感觉十分高大上，今天回顾这个题目的时候，突然有了顿悟，
有了递推的思想就容易解决了。
题意：给你n条直线，问：输出这些直线所有相交情况下的交点个数（升序输出）
解题思路：我们可以从n-1条直线相交的情况推导出n条直线的相交情况，考虑到直线的关系不是相交就是平行，我们可以推倒一下n=4的情况：
已知n=3时有0,2,3;
(1):第四条直线与前三条平行，则有0;
(2):第四条直线与其中两条平行，则有3;
(3):第四条直线与其中一条平行，则有4,5;
(4):第四条直线不与任何直线平行，则有3,5,6;
大致可以知道当有j条边与第n条直线不平行是时候有（n-j）*j加上j条直线的交点，
得出状态dp[j][j条边的交点]存在，得出状态dp[n][(n-j)*j+j条直线的交点]存在，
1 #include <stdio.h> 2 #include <string.h> 3 #define N 200//当n=20的时候交点数目最多为n*(n-1)/2 < 200 4 5 int dp[21][N];//dp[直线的总数][交点的个数] = 状态（本状态存在为1，否则为0） 6 int main () 7 { 8 int i, n, j, k; 9 for (i=0; i<21; i++)10 dp[i][0] = 1;//所有的直线都平行11 for (i=2; i<21; i++)//枚举n的值，并且打标12 for (j=1; j<i; j++)//枚举与i相交的边的数目13 for (k=0; k<N; k++)//枚举j条边的交点情况14 if (dp[j][k])//如果存在则推论成功15 dp[i][(i-j)*j+k] = 1;16 while (scanf ("%d", &n) != EOF)17 {18 for (i=0; i<N; i++)19 {20 if (dp[n][i])21 {22 if (i)23 printf (" ");24 printf ("%d", i);25 }26 }27 printf ("\n");28 }29 }
hdu 1466 计算直线的交点数 递推
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。