HDU 1466 計算直線的交點數

問題：求n根直線所組成的所有交點數。

分析：前3根直線都很好分析，很容易理解，所以我們從第三根再增加一根到第四根來分析，這裡能包含後面的所有情況
當n=4時：

 
1.四條直線全部平行，無交點2.其中三條平行，交點數: (n-1)*1 +0=3；3.其中兩條平行，而另外兩條直線的交點既可能平行也可能相交，因此交點數據分別為：     (n-2)*2+0=4，(n-2)*2+1=54. 四條直線互不平行， 交點數為(n-3)*3+3條直線的相交情況：                            (n-3)*3+0=3 ，(n-3)*3+2=5 ，(n-3)*3+3=6
發現：M條直線的交點方案數 = r 條直線交叉的交點數與(m-r)條平行線 + r 條直線本身的交點方案 = (m - r) * r  + r 條直線之間的交點數。AC代碼：

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int dp[21][202];

int main()
{
    int n,i,j;
    memset(dp,0,sizeof(dp));
    for(i = 0; i < 21; i++)
    {
        dp[i][0] = 1;      //1標記第i根線存在j(0)個點這種可能
    }
    for(n = 2; n < 21; n++)
    {
        for(i = 1; i < n; i++)
        {
            for(j = 0; j < 201; j++)
            {
                if(dp[n-i][j] == 1)  //如果n-i根線時存在j個點
                {
                    dp[n][j+i*(n-i)] = 1;
                }
            }
        }
    }
    while(scanf("%d",&n)!=EOF)
    {
        printf("0");  //所有的都有0個交點
        for(i = 1; i < 201; i++)
        {
            if(dp[n][i] == 1)
            {
                printf(" %d",i);
            }
        }
        printf("\n");
    }

    return 0;
}