（简单dp）hdu1466 计算直线的交点数

冷不防 2022-03-10 03:56 224阅读 0赞

题目链接：[（简单dp）hdu1466 计算直线的交点数][dp_hdu1466]

Problem Description

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

Input

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

Output

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

Sample Input

2 3

Sample Output

0 1 0 2 3

**题解：**蠢哭 ~ 现在看到个题目就害怕，看到个递推（也可以说是动态规划）就吓倒了。注意题目上说无三点共线！无三点共线！！无三点共线！！！（例如，三条线相交，没有平行线，那么交点个数唯一）知道这一点，盘他。

设dp\[i\]\[j\]表示i条直线j个交点的情况是否存在，存在的话值为1，否则0。

总的思路就是由前n-1条直线的相交情况推n条直线的相交情况。n条直线相交，因为每条直线最多有n-1个交点，而每个交点被算了两次，所以n条直线相交最多有n\*(n-1)个交点。

#include <iostream>
    #include <cstdio>
    using namespace std;
    const int maxn=25;
    int dp[maxn][200];
    
    void solve(){
    	for(int n=1;n<=20;n++){
    		dp[n][0]=1;
    		for(int k=1;k<=n;k++){
    			for(int i=0;i<=190;i++){
    				if(dp[k][i]){
    					dp[n][i+(n-k)*k]=1;   //n-k条平行线和k条线相交，增加了(n-k)*k个点 
    				}
    			}
    		}
    	}
    }
    
    int main(){
    	int n;
    	solve();
    	while(~scanf("%d",&n)){
    		printf("0");
    		for(int i=1;i<=190;i++){
    			if(dp[n][i]){
    				printf(" %d",i);
    			}
    		}
    		printf("\n");
    	}
    	return 0;
    }

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