动态规划入门——Humble Numbers

转载请注明出处：http://blog.csdn.net/a1dark

分析：这题其实就是一个求2、3、5、7的倍数的序数、求第N个能被2、3、5、7整除的值是多少、直接遍历每个值、然后求解的话会超时、所以选择优化、第I个值与第I-1个值有关、所以从前I-1个的2、3、5、7的倍数、来推出第I个值的大小、逆序可以取得较大的优化、

#include<stdio.h>
long long int dp[5843];
int prime[4]={2,3,5,7};
int main(){
    int n;
    dp[1]=1;
    for(int i=2;i<=5842;i++){
        dp[i]=2000000001;
        for(int j=0;j<4;j++){
            for(int k=i-1;k>=1;k--){//从后往前逆序优化
                if(dp[k]*prime[j]<=dp[i-1])break;//由于是从大到小的、如果小于等于前一个的话、就没有循环的必要
                if(dp[k]*prime[j]<dp[i])//求出满足要求的最小值
                    dp[i]=dp[k]*prime[j];
            }
        }
    }
    while(scanf("%d",&n)!=EOF){
        if(n==0)break;
        printf("The ");
        printf("%d",n);
        if(n%10==1&&n%100!=11)printf("st ");
        else if(n%10==2&&n%100!=12)printf("nd ");
        else if(n%10==3&&n%100!=13)printf("rd ");
        else printf("th ");
        printf("humble number is %lld.\n",dp[n]);
    }
    return 0;
}