首页 > 代码库 > HDU 1058 Humble Numbers
HDU 1058 Humble Numbers
既然将这道题分类到动态规划的题目里面,一开始便是用动态规划的思想去思考。
一个上午毫无突破,看的人家的题解。
定义四个伪指针存放下标,分别表示的意思是在已知的丑数中,能够与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> 6 using namespace std; 7 8 int dp[5850]; 9 10 inline int min(int a, int b, int c, int d)11 {12 a = min(a, b);13 c = min(c, d);14 return min(a, c);15 }16 17 void DP(void)18 {19 int i;20 int p1 = 1, p2 = 1, p3 = 1, p4 = 1;21 dp[1] = 1;22 for(i = 2; i <= 5842; ++i)23 {24 dp[i] = min(dp[p1] * 2, dp[p2] * 3, dp[p3] * 5, dp[p4] * 7);25 if(dp[i] == dp[p1] * 2)26 ++p1;27 if(dp[i] == dp[p2] * 3)28 ++p2;29 if(dp[i] == dp[p3] * 5)30 ++p3;31 if(dp[i] == dp[p4] * 7)32 ++p4;33 }34 } 35 36 int main(void)37 {38 #ifdef LOCAL39 freopen("1058in.txt", "r", stdin);40 #endif41 42 DP();43 int n;44 while(scanf("%d", &n) && n)45 {46 if(n % 10 == 1 && n % 100 != 11)47 printf("The %dst humble number is ", n);48 else if (n % 10 == 2 && n % 100 != 12)49 {50 printf("The %dnd humble number is ", n);51 }52 else if (n % 10 == 3 && n % 100 != 13)53 {54 printf("The %drd humble number is ", n);55 }56 else57 printf("The %dth humble number is ", n);58 59 printf("%d.\n", dp[n]);60 }61 return 0;62 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。