HDU 1466

经典DP，这样的递推确实有点难。 把所有直线分成两组，可以知道

m条直线的交点方案数 =（m-r）条平行线与r条直线交叉的交点数  + r条直线本身的交点方案 

亦就是  =（m-r）*r+r条之间本身的交点方案数（0<=r<m）；

#include <iostream>
#include <cstdio>
using namespace std;

bool ans[25][250];

int main(){
    memset(ans,false,sizeof(ans));
    for(int i=1;i<=20;i++){
        ans[i][0]=true;
        for(int r=0;r<=i;r++){
            for(int k=0;k<=r*(r-1)/2;k++)
            if(ans[r][k]){
                ans[i][(i-r)*r+k]=true;
            }
        }
    }
    int n;
    while(scanf("%d",&n)!=EOF){
        bool flag=false;
        for(int i=0;i<=n*(n-1)/2;i++){
            if(flag){
                if(ans[n][i])
                printf(" %d",i);
                continue;
            }
            else if(ans[n][i]){
                flag=true;  printf("%d",i);
            }
        }
        printf("
");
    }
    return 0;
}