C++ 计算直线的交点数（动态规划）

问题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1466

Problem Description

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

Input

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

Output

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

Sample Input

2 3

Sample Output

0 1 0 2 3

题目分析:

容易列举出N= 1,2,3的情况：

0,1

0,2,3

当N= 4时；

1.第四条与其余三条直线全部平行 -->无交点为 0；

2.第四条直线与其余两条直线平行-->交点数为（n-1）*1 +0 = 3；

3.第四题条直线与其余一条平行-->交点数为（n-2）*2 +0 = 4 、（n-2）*2 +1 = 5

4.第四题条直线与其余都不平行-->交点数为（n-3）*3 +0 = 3 、（n-3）*3 +2 = 5 、（n-3）*3 +3 = 6

规律：

m条直线的交点方案数
=（m-r）条平行线与r条直线交叉的交点数
+ r条直线本身的交点方案
=（m-r）*r+r条之间本身的交点方案数（1<=r<=m）

/*
平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
*/
#include<iostream>
using namespace std;
//行数代表几条线，列数代表交点数，当dp[i][j]==1时,代表存在

int dp[21][200] = {};//N条线最多 n*(n-)/ 2个交点          

int main()
{
    int N,b;
    while(cin>>N)
    {
        dp[0][0] = dp[1][0] =  1;//n =0和n = 1的情况
        for(int n = 2;n<=N;n++) //代表n条线
        {
            dp[n][0] = 1;   //n条直线都平行时交点为0

            for(int i=0;i<n;i++)//i表示n条直线有i条平行
            {
                
                for(int j=0;j<=n*(n-1)/2;j++)//j表示交点数
                {
                    b = n - i -1; //b为n条直线减去平行线
                    if(dp[b][j] == 1)
                        dp[n][(n-b)*b+j] = 1;//m条直线的交点方案数 = （m-b）*b+b条之间本身的交点方案数（1<=r<=m）

                }
            }
        }
        
        for(int j=0;j<N*(N-1)/2;j++)
        {
            if(dp[N][j] == 1)
                cout<<j<<" ";
        }
        cout<<N*(N-1)/2<<endl;
        
    }
    return 0;
}

C++ 计算直线的交点数（动态规划）

相关推荐