/********************************* * 日期:2011-3-10 * 作者:SJF * 题号:杭电1058 * 题目:Humble Numbers * 结果:AC * 题意: * 总结:DP问题 **********************************/ #include<stdio.h> #define N 5843 int f[N]; int min(int a,int b,int c,int d) { int x=a>b?b:a; int y=c>d?d:c; int m=y>x?x:y; return m; } int main() { int a,b,c,d,i,n; a=b=c=d=1; f[1]=1; for(i=2;i<=N;i++) { f[i]=min(f[a]*2,f[b]*3,f[c]*5,f[d]*7); if(f[i]==f[a]*2) a++; if(f[i]==f[b]*3) b++; if(f[i]==f[c]*5) c++; if(f[i]==f[d]*7) d++; } while(scanf("%d",&n)!=EOF&&(n!=0)) { if(n%100==11||n%100==12||n%100==13) printf("The %dth humble number is %d.\n",n,f[n]); else { if(n%10==1) printf("The %dst humble number is %d.\n",n,f[n]); else if(n%10==2)printf("The %dnd humble number is %d.\n",n,f[n]); else if(n%10==3)printf("The %drd humble number is %d.\n",n,f[n]); else printf("The %dth humble number is %d.\n",n,f[n]); } } return 0; }