题目: http://acm.hdu.edu.cn/showproblem.php?pid=1466
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; int main()
{
int n;
int r; //假设有r条非相互平行的线。
int dp[][];
memset(dp, , sizeof(dp));
for(int i=; i<=; i++)
{
dp[i][] = ;
for(r=; r<=i; r++)
{
for(int j=; j<=; j++)
{
if(dp[r][j]==)
dp[i][(i-r)*r+j] = ;
}
}
}
while(scanf("%d", &n)!=EOF)
{
for(int j=; j<=n*(n-)/; j++)
{
if(dp[n][j]==)
{
if(j!=)
cout<<" ";
cout<<j;
}
}
cout<<endl;
}
return ;
}
状态转移方程:
m条直线的交点方案数
=(m-r)条平行线与r条直线交叉的交点数 + r条直线本身的交点方案
=(m-r)*r+r条之间本身的交点方案数(0<=r<m)
(百度: 刘春英课件(1) 有详解)。