【HDU 1058 & HDU 3199 类似丑数】简单DP思想

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1058（1058）

http://acm.hdu.edu.cn/showproblem.php?pid=3199 （3199）

题目大意：给你四个素数2,3,5,7，只由它们四个组成合数，对这些合数从大到小进行排列，求第n个合数的大小。

解题思路：

一看到这题，开始想要暴力，从1到Max进行横扫遍历，ok这题暴力没问题1171ms，因为题目给了限制n最大只有5842，如果我给的数很大呢，比如n=100000，暴力明显TLE。

所以这题我们要换种思路，因为题目只给了4个数（如果题目没给素数排好序，则应该先排序），所以答案必由这四个数组成，我们记这个数的组成方式为2^a*3^b*5^c*7^d,比如1为0000，630为1211，即2*3*3*5*7. 所以我们可以用a，b，c，d分别记录2,3,5,7出现的次数，这样做的好处就是可以利用前面计算的结果按顺序推出后面的结果，如果你对过程还不是很熟悉，列几个先试试。

小提醒：1.遇见这样的字母输出千万要注意观察规律，藐视我看了很久。

2.不确定大小的数最好用__int64代替int。

3.题目给的素数已经确定，可以选择打表，效率提高很多。

4.千万要淡定，一种方式行不通可以考虑其他方法，藐视我开始是胡搞中间总是少几个数，果然换一种写法。

1058：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int maxn=5843;
 8 __int64  f[maxn];
 9 
10 __int64 Min(__int64 a, __int64 b, __int64 c,__int64 d)
11 {
12     a=min(a,b);
13     a=min(a,c);
14     a=min(a,d);
15     return a;
16 }
17 
18 int main()
19 {
20     f[0]=1;
21     int a=0, b=0, c=0, d=0;
22     for(int i=1; i<maxn; i++)  //打表
23     {
24         f[i]=Min(f[a]*2,f[b]*3,f[c]*5,f[d]*7);   //这里我们用到一点动态规划思想，每次只取前面记录的最小值，依次类推
25         if(f[i]==f[a]*2) a++;  //2出现的次数
26         if(f[i]==f[b]*3) b++;  //3出现的次数
27         if(f[i]==f[c]*5) c++;  //5出现的次数
28         if(f[i]==f[d]*7) d++;  //7出现的次数
29     }
30     int  n;
31     while(~scanf("%d",&n),n)
32     {
33         if(n%100==11||n%100==12||n%100==13)
34             printf("The %dth humble number is %I64d.\n",n,f[n-1]);
35         else
36         {
37             if(n%10==1)
38                 printf("The %dst humble number is %I64d.\n",n,f[n-1]);
39             else if(n%10==2)
40                 printf("The %dnd humble number is %I64d.\n",n,f[n-1]);
41             else if(n%10==3)
42                 printf("The %drd humble number is %I64d.\n",n,f[n-1]);
43             else
44                 printf("The %dth humble number is %I64d.\n",n,f[n-1]);
45         }
46     }
47     return 0;
48 }

3199（记得给素数先排序）：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int maxn=1000001;
 8 __int64  f[maxn];
 9 
10 __int64 Min(__int64 a, __int64 b, __int64 c)
11 {
12     a=min(a,b);
13     a=min(a,c);
14     return a;
15 }
16 
17 int main()
18 {
19     __int64  s[3], n, a, b, c;
20     while(scanf("%I64d%I64d%I64d%I64d",&s[0],&s[1],&s[2],&n)!=EOF)
21     {
22         sort(s,s+3);
23         f[0]=1;
24         a=b=c=0;
25         for(int i=1; i<=n; i++)
26         {
27             f[i]=Min(f[a]*s[0],f[b]*s[1],f[c]*s[2]);
28             if(f[i]==f[a]*s[0]) a++;
29             if(f[i]==f[b]*s[1]) b++;
30             if(f[i]==f[c]*s[2]) c++;
31         }
32         printf("%I64d\n",f[n]);
33     }
34     return 0;
35 }

【HDU 1058 & HDU 3199 类似丑数】 简单DP思想

【HDU 1058 & HDU 3199 类似丑数】简单DP思想