HDU 1466直線の交差点数(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 Solutionはn本の線を互いに平行な線i本と平行でない線n-i本(ここでの平行でないのはそのi本の平行線と平行でないことを指す)に分割し、dp[x][y]でx本の線がy個の交点を形成できるかどうかを表す(dp[x][0]=1,dp[x][y]=0(y!=0)))、dp[n-i][k]=1であれば、dp[n][k+i*(n-i)]=1である.線の本数が20本を超えないため、交も200 200を超えず、交も200[n-i][n-i][k][k][k]=0]=1である個、従って、dp配列を前処理する場合、第1のループ列挙線の本数、第2のループ列挙平行線の本数、第3のループ列挙交点個数、総複雑度はO(20*20*200)であり、Codeを完全に受け入れることができる

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
bool dp[22][222];
void goto_dp()
{
    for(int i=0;i<22;i++)
        dp[i][0]=1;
    for(int i=2;i<22;i++)//  
        for(int j=1;j<=i;j++)//  
            for(int k=0;k<222;k++)// i-j  
                if(dp[i-j][k])// i-j k , j k+j*(i-j)  
                    dp[i][k+j*(i-j)]=1;                 
}
int main()
{
    memset(dp,0,sizeof(dp));//  
    goto_dp();//  
    int n;
    while(~scanf("%d",&n))
    {
        int first=1;//  
        for(int i=0;i<222;i++)// n i  
        {
            if(dp[n][i]&&first)
                printf("%d",i),first=0;
            else if(dp[n][i])
                printf(" %d",i);
        }
        printf("
");
    }
    return 0;
}