HDOJ(HDU).1058 Humble Numbers (DP)

点我挑战题目

题意分析

水

代码总览

/*

    Title:HDOJ.1058

    Author:pengwill

    Date:2017-2-15

*/

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define nmax 6000

#define min(a,b) (a<b?a:b)

#define min4(a,b,c,d) min(min(a,b),min(c,d))

using namespace std;

int r[nmax];

int a = 1,b=1,c=1,d=1,len,tail;

int main()

{

    r[1] =1;

    for(int i = 2; i<=5842;++i){

        r[i] = min4(2*r[a],3*r[b],5*r[c],7*r[d]);

        if(r[i] == 2*r[a]) a++;

        if(r[i] == 3*r[b]) b++;

        if(r[i] == 5*r[c]) c++;

        if(r[i] == 7*r[d]) d++;

    }

    int t;

    while(scanf("%d",&t) && t ){

         printf("The %d", t);

         if(t%10 == 1 && t%100 != 11) printf("st ");

         else if(t%10 == 2 && t%100 != 12) printf("nd ");

         else if(t%10 == 3 && t%100 != 13) printf("rd ");

         else printf("th ");

         printf("humble number is %d.\n", r[t]);

    }

    return 0;

}