首页 / 更多教程 / HDU 1058 Humble Numbers

HDU 1058 Humble Numbers

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了HDU 1058 Humble Numbers，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1716字，纯文字阅读大概需要3分钟。

内容图文

既然将这道题分类到动态规划的题目里面，一开始便是用动态规划的思想去思考。

一个上午毫无突破，看的人家的题解。

定义四个伪指针存放下标，分别表示的意思是在已知的丑数中，能够与2，3，5，7相乘的最小的数的下标。

上面这句话要好好体会。

也就是说dp[p1] * 2 能够得到一个新的丑数，其他三个以此类推。

但我们要求的是已知最大丑数中紧挨着的下一个丑数，那就是能够产生新丑数的最小值了。

即min(dp[p1] * 2, dp[p2] * 3, dp[p3] * 5, dp[p4] * 7);

 

另外需要注意的一点是，在DP()中会遇到某两个产生的丑数同为最小值的情况，那么对应的“指针”也要同时自增1。

比如i = 5的时候，p1 = 3, p2 = 2,此时dp[p1] * 2 == dp[p2] * 3 == 6；

如果只执行++p1不执行++p2的话，那么会漏掉9这个丑数。

 

最后吐槽一下蛋疼的输出。。

╮(╯▽╰)╭，何时才能不看题解，通过自己思考把dp题目A出来呢。。

 

                 1
                //
                #define LOCAL
                 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6usingnamespace std;
 7 8int dp[5850];
 910 inline int min(int a, int b, int c, int d)
11{
12     a = min(a, b);
13     c = min(c, d);
14return min(a, c);
15}
1617void DP(void)
18{
19int i;
20int p1 = 1, p2 = 1, p3 = 1, p4 = 1;
21     dp[1] = 1;
22for(i = 2; i <= 5842; ++i)
23    {
24         dp[i] = min(dp[p1] * 2, dp[p2] * 3, dp[p3] * 5, dp[p4] * 7);
25if(dp[i] == dp[p1] * 2)
26             ++p1;
27if(dp[i] == dp[p2] * 3)
28             ++p2;
29if(dp[i] == dp[p3] * 5)
30             ++p3;
31if(dp[i] == dp[p4] * 7)
32             ++p4;
33    }
34} 
3536int main(void)
37{
38    #ifdef LOCAL
39         freopen("1058in.txt", "r", stdin);
40#endif4142    DP();
43int n;
44while(scanf("%d", &n) && n)
45    {
46if(n % 10 == 1 && n % 100 != 11)
47             printf("The %dst humble number is ", n);
48elseif (n % 10 == 2 && n % 100 != 12)
49        {
50             printf("The %dnd humble number is ", n);
51        }
52elseif (n % 10 == 3 && n % 100 != 13)
53        {
54             printf("The %drd humble number is ", n);
55        }
56else57             printf("The %dth humble number is ", n);
5859         printf("%d.\n", dp[n]);
60    }
61return0;
62 }
代码君

 

原文：http://www.cnblogs.com/AOQNRMGYXLMV/p/3824580.html

内容总结

以上是互联网集市为您收集整理的HDU 1058 Humble Numbers全部内容，希望文章能够帮你解决HDU 1058 Humble Numbers所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1323440.html

来源：【匿名】