HDU-1058 Humble Numbers 暴力 Or 动态规划-白红宇

HDU-1058 Humble Numbers 暴力 Or 动态规划

阅读量：6573 次

发布时间：2019-06-24

本文共 2446 字，大约阅读时间需要 8 分钟。

题目意思很好懂。

暴力的想法是在已知的丑数中选出最小的，保存之，然后乘以2，3，5，7保存起来，这里要注意去重。不得不说其英文输出很坑爹。

代码如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #define MAXN 5850using namespace std;int n, a[4] = { 2, 3, 5 ,7};long long ans[MAXN]; priority_queue
           
            , greater
            
              > q;map
             
               mp;void pre(){ int pos = 1, cnt = 0; q.push(pos); mp[1] = 1; while (1) { long long pos = q.top(); ans[++cnt] = pos; if (cnt >= 5842) { break; } q.pop(); for (int i = 0; i < 4; ++i) { if (!mp.count(pos*a[i])) { q.push(pos*a[i]); mp[pos*a[i]] = 1; } } }}int main(){ pre(); while (scanf("%d", &n), n) { if (n % 10 == 1 && n%100 != 11) { printf("The %dst humble number is ", n); } else if (n % 10 == 2 && n%100!= 12) { printf("The %dnd humble number is ", n); } else if (n % 10 == 3 && n%100 != 13) { printf("The %drd humble number is ", n); } else { printf("The %dth humble number is ", n); } cout << ans[n] << "." << endl; } return 0;}

还有一种思想就是动态规划的思想，也是看了大牛的代码后知道的。定义4个伪指针p1, p2, p3, p4指向数组下标，分别表示的意思是在已知的丑数中，能够与2，3，5，7相乘的最小的数的下标。比如说已知第一个数是1，那么能够和2相乘的最小数就是1（p1指向其数组下标）了。同理，在已知2是由1*2得到后，就不能再用1*2来生成2了，因为这样没有意思，此时就p1就指向了2所在的下标了。每次新增加的丑数就是 Min(num[p1]*2, num[p2]*3, num[p3]*5, num[p4]*7) 了。

代码如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int dp[5850];inline int Min(int a, int b, int c, int d){    return min(a, min(b, min(c, d)));}void DP(){    int p1 = 1, p2 = 1, p3 = 1, p4 = 1;    dp[1] = 1;    for (int i = 2; i <= 5842; ++i) {        dp[i] = Min(dp[p1]*2, dp[p2]*3, dp[p3]*5, dp[p4]*7);        if (dp[i] == dp[p1]*2) {            ++p1;        }        if (dp[i] == dp[p2]*3) {            ++p2;        }        if (dp[i] == dp[p3]*5) {            ++p3;        }        if (dp[i] == dp[p4]*7) {            ++p4;        }    }}int main(){    int n;    DP();    while (scanf("%d", &n), n) {        if (n % 10 == 1 && n%100 != 11) {            printf("The %dst humble number is ", n);        }        else if (n % 10 == 2 && n%100!= 12) {            printf("The %dnd humble number is ", n);        }        else if (n % 10 == 3 && n%100 != 13) {            printf("The %drd humble number is ", n);        }        else {             printf("The %dth humble number is ", n);        }        printf("%d.\n", dp[n]);    }        return 0;}

转载于:https://www.cnblogs.com/Lyush/archive/2012/05/02/2479347.html

你可能感兴趣的文章