zoj 1095 Humble Numbers(醜數+dp)

【題目大意】：将一些僅含有因子2，3，5，7的數是Humble Number，給出一個n，輸出第n個Humble Numbers

【解題思路】：醜數的類型題。可用dp解。

                            我們用ugly[i]表示第i+1個Humble Number，用cnt[i]表示第i個因子現在擴充到cnt[i]這個位置...

                            我們可以得到ugly[i]=min(x[j]*cnt[j]) x[j]為因子，即2，3，5，7

                            然後每一次擴充後，将cnt[j]+1.....

    注意，不要單純加最後得到轉移至ugly[i]的cnt值。例如：

                           ugly：1 2 3 4 5

                           cnt: 2 1 1 0

                           那麼下一個ugly可以分别由ugly[a[0]]*2,和ugly[a[1]]*3得到...是以為了去重，兩個對應的cnt都要+1....-_-!!!!

【代碼】：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <cctype>
#include <map>
#include <iomanip>
                   
using namespace std;
                   
#define eps 1e-8
#define pi acos(-1.0)
#define inf 1<<30
#define linf 1LL<<60
#define pb push_back
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
#define lowbit(x) (x & (-x))
#define ll long long

int ugly[6100];
int cnt[4];
int x[4]={2,3,5,7};


void solve_ugly_number(){
    ugly[0]=1;
    memset(cnt,0,sizeof(cnt));
    for (int i=1; i<5842; i++){
        for (int j=0; j<4; j++) 
            if (ugly[i]!=0) ugly[i]=min(ugly[i],x[j]*ugly[cnt[j]]);
            else ugly[i]=x[j]*ugly[cnt[j]];
        for (int j=0; j<4; j++) {
            if (ugly[i]==x[j]*ugly[cnt[j]]) cnt[j]++;
        }
    }
    return ;
}

int main(){
    int n;
    solve_ugly_number();
    while(~scanf("%d",&n)){
        if (n==0) break;    
        if(n%10==1 && n%100!=11)
            printf("The %dst humble number is %d.\n",n,ugly[n-1]);
        else if(n%10==2 && n%100!=12 )
            printf("The %dnd humble number is %d.\n",n,ugly[n-1]);
        else if(n%10==3 && n%100!=13)
            printf("The %drd humble number is %d.\n",n,ugly[n-1]);
        else printf("The %dth humble number is %d.\n",n,ugly[n-1]);                
    }
    return 0;
}