DP+数学——直線の交差点数を計算する

Description

平面の上でn本の直線があって、しかも3線の共点がなくて、これらの直線に何種類の異なる交差点があることができるかを聞きます.例えば、n=2の場合、可能な交点数は0(平行)または1(非平行)である.

Input

入力データは複数の試験例を含む、各試験例は1行を占め、各行は正の整数n(n<=20)を含み、nは直線の数を表す.

Output

各テストインスタンスは1行の出力に対応し、各数が可能な交差点数であり、各行の整数間にスペースで区切られたすべての交差スキームを小さいから大きいまでリストします.

Sample Input

2

3

Sample Output

0 1

0 2 3

HINT

n本の直線の最も多い交差点数はn(n-1)/2で、仮にその線があって、i本の平行線、自由線の交差点数はkで、それではn本の線の交点は(i-j)*j+kに等しい

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

    int dp[21][400];// i j 

    int main()

    {

        int n;

       while(~scanf("%d",&n)){

            memset(dp,0,sizeof(dp));

            for(int i = 0; i <= 21 ;i++)

               dp[i][0] = 1;

            for(int i = 1; i <= 21;i++){

                for(int j = 0; j < i;j++){// 

                    for(int k = 0; k < 191;k++){

                        if(dp[i-j][k] == 1)

                        dp[i][(i-j)*j+k] = 1;

                    }

                }

            }

            printf("0");

            for(int i = 1; i <= 190; i++){

                    if(dp[n][i] == 1)

                    printf(" %d",i);

            }

       puts("");

     }

       return 0;

}