HDU 1058 Humble Numbers

http://acm.hdu.edu.cn/showproblem.php?pid=1058

话说这题是动态规划的吧. 刚开始就想到的是直接暴力, 用一个有序数列.

数列的最开头的数字是最小的,然后将它乘以2,3,5,7后得到的数字放回数列中,同时将第一个数字出列....

然后只要出了5842个数字就刚好了.

set 容器刚好满足 1.去重, 2.排序

View Code

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <set>
 4 using namespace std;
 5 const int maxn = 5843;
 6 set<long long> ans;
 7 long long temp[maxn];
 8 int main()
 9 {
10     int i, j, n;
11     long long k;
12     temp[1]=1;
13     ans.insert(2);
14     ans.insert(3);
15     ans.insert(5);
16     ans.insert(7);
17     set<long long>::iterator iter;
18     for(i=2;i<=5842;i++)
19     {
20         iter = ans.begin();
21         temp[i] = *iter;
22         k = *iter;
23         ans.insert(2*k);
24         ans.insert(3*k);
25         ans.insert(5*k);
26         ans.insert(7*k);
27         ans.erase(iter);
28     }
29     while(~scanf("%d",&n),n){
30         if(n%100==11 || n%100==12 || n%100==13){
31             printf("The %dth humble number is %lld.\n",n,temp[n]);
32         }
33         else if(n%10==1){
34             printf("The %dst humble number is %lld.\n",n,temp[n]);
35         }
36         else if(n%10==2){
37             printf("The %dnd humble number is %lld.\n",n,temp[n]);
38         }
39         else if(n%10==3){
40             printf("The %drd humble number is %lld.\n",n,temp[n]);
41         }
42         else{
43             printf("The %dth humble number is %lld.\n",n,temp[n]);
44         }
45     }
46     return 0;
47 }