hdu1058 参考答案

   1 /*
   2 hdu1058 Humble Numbers DP
   3 ymc 2008/9/23
   4 题目大意：
   5 如果一个数的没有2，3，5，7以外的质因子，则这个数
   6 称为Humble数。前几个Humble数为
   7 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18,
   8 20, 21, 24, 25, 27, ...
   9 求第n个Humble数。
  10 分析与解题思路：
  11 Humble数没有2，3，5，7以外的质因子，则
  12 令h[]记录已经求到的Humble数，假设已经求了num个。
  13 则把所有h[]中的数乘以2，3，5，7得到的最小大于h[num]的
  14 数就是下一个Humble数。但这样无疑会TLE。
  15 Prim[4]={2,3,5,7}
  16 初始id[4]={1,1,1,1}
  17 其中id[k]为h[]中的下标。表示乘以2的Humble数在h[]中的下标。
  18 已经知道num个Humble数时，min{Prim[k]*H[id[k]},0<=k<=3，
  19 就是要找的下一个Humble数。
  20 注意重复的情况。
  21 */
  22 #include <iostream>
  23 #include <limits>
  24 using namespace std;
  25 const int N=5843;
  26 int num;
  27 double Prim[4]={2,3,5,7};
  28 int id[4]={1,1,1,1};//初始下标
  29 int h[N];
  30 char s[4][3]={"th","st","nd","rd"};
  31 int  Humble()//求下一个Humble数，
  32 {
  33     double Max=INT_MAX;//double类型，乘积可能会超出int。
  34     double tmp;
  35     int k;
  36     for(int i=0;i<4;i++)
  37     {
  38         tmp=Prim[i]*h[id[i]];
  39         if(tmp<Max)
  40         {
  41             Max=tmp;
  42             k=i;
  43         }
  44     }
  45     id[k]++;
  46     return int(Max);
  47 }
  48 void Init()
  49 {
  50     h[1]=1;
  51     num=1;
  52     for(num=2;num<N;num++)
  53     {
  54         h[num]=Humble();
  55         if(h[num]==h[num-1])//重复，重新再求。
  56             num--;
  57     }
  58 }
  59 void OutPut(int n)//输出，11，12，13特殊，其它1，2，3结尾的普通。
  60 {
  61     int k=0;
  62     if(n%10==1&&n%100!=11)
  63         k=1;
  64     else if(n%10==2&&n%100!=12)
  65         k=2;
  66     else if(n%10==3&&n%100!=13)
  67         k=3;
  68     printf("The %d%s humble number is %d.\n",n,s[k],h[n]);
  69 }
  70 int main()
  71 {
  72     int n;
  73     Init();
  74     while(scanf("%d",&n),n)
  75     {
  76         OutPut(n);
  77     }
  78 }