计算直线的交点数
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8419 Accepted Submission(s): 3793
Problem Description
平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
Input
输入数据包含多个测试实例,每个测试实例占一行,每行包含一个正整数n（n<=20）,n表示直线的数量.
Output
每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数,每行的整数之间用一个空格隔开。
Sample Input
2 3
Sample Output
0 1 0 2 3
Author
lcy
Source
解题思路：
这道题其实不难，也就是个打表dp吧。。。但是做了快1小时，才A。。。
代码：
# include<cstdio>
# include<iostream>
using namespace std;
int a[29][199];
void dabiao()
{
for ( int i = 0;i <= 20;i++ )
{
a[i][0] = 1;
}
for ( int i = 1;i <= 20;i++ )
{
for ( int j = 0;j < i;j++ )
{
for ( int k = 0;k <= 190;k++ )
{
if ( a[i-j][k] == 1 )
{
a[i][(i-j)*j+k] = 1;
}
}
}
}
}
int main(void)
{
dabiao();
int n;
while ( cin>>n )
{
cout<<"0";
for ( int i = 1;i <= 190;i++ )
{
if ( a[n][i] == 1 )
{
cout<<" "<<i;
}
}
cout<<endl;
}
return 0;
}
Q神的代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
bool p[405];
void dfs(int tot,int now,int res)
{
if(tot==0)p[res]=1;
for(int i=now;i>=1;i--)
{
if(i<=tot)
{
dfs(tot-i,i,res+i*i);
}
}
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(p,0,sizeof(p));
dfs(n,n,0);
bool flag=1;
for(int i=n*n;i>=1;i--)
{
if(p[i])
{
if(!flag)printf(" %d",(n*n-i)/2);
else
{
printf("%d",(n*n-i)/2);
flag=0;
}
}
}
printf("\n");
}
return 0;
}