HDU1058 Humble Numbers 暴力 Or 动态规划

题目意思很好懂。

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

代码如下：

#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <map>
#include <iostream>
#define MAXN 5850
using namespace std;

int n, a[4] = {2, 3, 5 ,7};
long long ans[MAXN];  


priority_queue<long long, vector<long long>, greater<long long> > q;

map<long long,bool> 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 <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
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;
}