题目都是中文的,好懂。一开始当作树形dp去做,wa了,发现有些情况还没考虑到。

一下是摘自Even的题解

n条直线互不平行且无三线共点的最多交点数max=1+2+……(n-1)=n(n-1)/2,

所以n=20的话,最大的交点数是190

本题是求有多少种交点数:

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

0

0,1

0,2,3

如果已知<N的情况,我们来分析加入第N条直线的情况(这里N=4):

1、第四条与其余直线全部平行 => 无交点;

2、第四条与其中两条平行,交点数为(n-1)*1+0=3;

3、第四条与其中一条平行,这两条平行直线和另外两点直线的交点数为(n-2)*2=4,而另外两条直线既可能平行也可能相交,因此可能交点数为:(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

即n=4时,有0个,3个,4个,5个,6个不同交点数。

从上述n=4的分析过程中,我们发现:

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


代码:

StatusAccepted
Memory1748kB
Length829
LangC++
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=25;
const int maxm=200;
int ans[maxm], up, n;
int dp[maxn][maxm];
inline int max(int a, int b){return a>b?a:b;}
int main()
{
    memset(dp, 0, sizeof(dp));
    dp[0][0]=1;dp[1][0]=1;
    for(int i=2;i<=20;i++){
        dp[i][0]=1;
        for(int j=1;j<i;j++){
            for(int k=0;k<=dp[j][0];k++){
                if(dp[j][k]){   //如果前j条的k个交点组合存在
                    dp[i][(i-j)*j+k]=1;
                    dp[i][0]=max(dp[i][0], (i-j)*j+k);
                }
            }
        }
    }
    while(~scanf("%d",&n)){
        for(int i=0;i<=dp[n][0];i++){
            if(dp[n][i]){
                printf("%d", i);
                if(i!=dp[n][0])printf(" ");
            }
        }
        printf("\n");
    }
    return 0;
}