Time Limit:1000MS Memory Limit:65536K
Total Submit:0 Accepted:0

Description

平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。

Input

输入数据包含多个测试实例,每个测试实例占一行,每行包含一个正整数n（n <= 20）,n表示直线的数量.

Output

每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数,每行的整数之间用一个空格隔开。

Sample Input

2
3

Sample Output

0 1
0 2 3
大家用什么算法实现
可以到这里提交 http://acm.hdu.edu.cn/search.php?field=problem&key=1466

各位兄弟姐妹帮帮我啊！~

DP

/**
* Writtern By Eastsun
* 2007/8/8
*/
#include<stdio.h>
#define MAX 20
char flags[MAX+1][(MAX+1)*MAX/2];
int main(){
    int i,j,k;
    for(i =1;i<=MAX;i++){
        flags[i][0] =1;
        for(j =1;j<i;j++)
            for(k =0;k<=(i-j)*(i-j-1)/2;k++)
                flags[i][j*(i-j)+k] |= flags[i-j][k];
    }
    while(scanf(\"%d\",&i)!=EOF){
        for(k=0;k<i*(i-1)/2;k++)
            if(flags[i][k]) printf(\"%d \",k);
        printf(\"%d\n\",i*(i-1)/2);
    }
    return 0;
}

for(k =0;k<=(i-j)*(i-j-1)/2;k++)
flags[i][j*(i-j)+k] |= flags[i-j][k];
能解释下这句什么意思么？
还有flags[i][j*(i-j)+k] |= flags[i-j][k];这里的|=是什么，为什么我改成flags[i][j*(i-j)+k] = flags[i-j][k];
结果好象是一样的呢

Eastsun 斑竹永远是这么的简单
除了赞一个也只能赞一个

大哥 ,你赞完能不能帮我解释下呢

flag[i][j]
i代表的是第i条线,j代表的是i条线j个不同点是不是可能.
|是位或
中间那个flag[i][i*(i-j)+k]|=flag[i-j][k];
应该不能直接等于.因为flag[i][i*(i-j)+k]可以由多中状态转移过,任何一种满足就可以了.之所以写成等于号也可以A通过可能是因为i<20
导致i*(i-j)+k只能唯一拆分成一对j,k

[此贴子已经被作者于2007-8-8 21:35:41编辑过]