hdu1466 参考答案

   1 /*
   2 hdu 1466 DP：计算直线的交点数
   3 ymc 2008/09/22
   4 题目大意：
   5 平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
   6 比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
   7 分析与解题思路：
   8 n条直线的交点数记为ans[n](多个可能的取值)。
   9 记最后一条直线为p，则与p平行的直线数(包括p本身)有r条(1<=r<=n)
  10 r=n时，交点数为0。
  11 1<=r<n时，s=n-r,则交点数为ans[n]=r*s+ans[s]。
  12 */
  13 
  14 #include <iostream>
  15 using namespace std;
  16 const int N=22;
  17 bool ans[N][N*N];
  18 
  19 void Init_n(int n)//n条直线的交点数
  20 {
  21     int tmp;
  22     ans[n][0]=true;//n条直线平行，交点数为0
  23     for(int r=1;r<n;r++)//有r条与p平行(包括p本身)
  24     {
  25         int s=n-r;//剩下s条与p不平行
  26         tmp=s*(s-1)/2;
  27         for(int j=0;j<=tmp;j++)
  28         {
  29             if(ans[s][j]==false)
  30                 continue;
  31             ans[n][r*s+j]=true;
  32         }
  33     }
  34 }
  35 void Init()
  36 {
  37     memset(ans,0,sizeof(ans));
  38     ans[0][0]=true;
  39     ans[1][0]=true;
  40     ans[2][0]=ans[2][1]=true;
  41     for(int n=3;n<N;n++)
  42         Init_n(n);
  43 }
  44 
  45 void OutPut(int n)//输出
  46 {
  47     int tmp=n*(n-1)/2;
  48     printf("0");
  49     for(int i=1;i<=tmp;i++)
  50     {
  51         if(ans[n][i])
  52             printf(" %d",i);
  53     }
  54     printf("\n");
  55 }
  56 int main()
  57 {
  58     Init();
  59     int n;
  60     while(scanf("%d",&n)!=EOF)
  61     {
  62         OutPut(n);
  63     }
  64 }