【题目大意】:将一些仅含有因子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;
}