首页 > ACM题库 > HDU-杭电 > HDU 1466 计算直线的交点数-动态规划-[解题报告] C++
2013
12-11

HDU 1466 计算直线的交点数-动态规划-[解题报告] C++

计算直线的交点数

问题描述 :

平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。

输入:

输入数据包含多个测试实例,每个测试实例占一行,每行包含一个正整数n(n<=20),n表示直线的数量.

输出:

每个测试实例对应一行输出,从小到大列出所有相交方案,其中每个数为可能的交点数,每行的整数之间用一个空格隔开。

样例输入:

2
3

样例输出:

0 1
0 2 3

 

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

 

解题思路:这道题是一道动态规划的题目,从4根线开始都是在之前N根线的组合的基础上演化而来的。其实N根线有多少的交点,就是看线的排布决定的。假设有N根线要相交,我们假设这N根线中有N-i条线是平行的,则有i条线是自由的,不跟这N-i条线平行,则这i条线中的每一条一定跟N-i条相平行的线有N-i个交点,所以i条自由线至少跟N-i条线有,i*(N-i)个交点,其中这i条线又有各自不同的相交情况,所以我们就可以看出其实这是个动态规划的问题了。最后我们只要根据线的数量分别用插入排序排好交点数就好,最好输出就是了。

 

根据上面所说,我们可以有以下的公式:

 

tem = (N-i)*i

val = tem+dp[i][k]

 

dp[i][k]表示的是i条边,它的k种交点个数。

 

#include <stdio.h>

int main()
{
	int i,j,k,g,tem,val,length,n,locate;
	const int size = 201;
	int dp[21][size];
	int len[21]={0,0,2,3};
	bool flag;
	dp[2][0] = 0,dp[2][1] = 1;
	dp[3][0] = 0,dp[3][1] = 2,dp[3][2] = 3;
	/*打表*/
	for (i=4;i<=20;i++)
	{
		dp[i][0] = 0;/*N根线都平行,则交点为0*/
		dp[i][1] = i-1;/*有N根线,N-1条线平行,剩下的一条线,则肯定跟这N-1条线有N-1个交点*/
		dp[i][2] = i*(i-1)/2;/*N根线最多有这么多的交点*/
		len[i] = 3;
	}
	for (i=4;i<=20;i++)
	{
		for (j=i-2;j>=2;j--)
		{
			tem = (i-j)*j;/*i-j条边平行,j条边自由*/
			for (k=0;k<len[j];k++)
			{
				val = tem+dp[j][k];/*某种交点个数*/
				/*插入排序*/
				locate = len[i]-1;
				flag = true;
				for (g=0;g<len[i];g++)
				{
					if (dp[i][g]>val)
					{
						locate = g;
						break;
					}
					else if(dp[i][g] == val)
					{
						flag = false;/*标记当前交点个数已经在表中*/
						break;
					}
				}
				if(!flag)/*表中已存在该值,则不插入*/
					continue;
				if(locate==len[i]-1)/*如果val是当前表中最大的,则插入到表末尾*/
				{
					dp[i][len[i]] = dp[i][locate];
					dp[i][locate] = val;
				}
				else/*插入表中央*/
				{
					for (g=len[i]-1;g!=locate-1;g--)
						dp[i][g+1] = dp[i][g];
					dp[i][locate] = val;
				}				
				len[i]++;/*更新长度*/
			}
		}
	}
	while (scanf("%d",&n)!=EOF)
	{
		length = len[n];
		for (i=0;i<length;i++)
		{
			if(i)
				printf(" ");
			printf("%d",dp[n][i]);
		}
		printf("/n");
	}
	return 0;
}

 

解题报告转自:http://blog.csdn.net/q3498233/article/details/5295113


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  3. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。