欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【简单动态规划dp+打表+输出格式】HDU-1058 Humble Numbers

程序员文章站 2024-01-23 23:25:10
...

【简单动态规划dp+打表+输出格式】HDU-1058 Humble Numbers
【简单动态规划dp+打表+输出格式】HDU-1058 Humble Numbers

注解

1、简单动态规划dp:初始4个值a,b,c,d,分别表示2,3,5,7的个数。然后每次从上一个abcd所在的值分别乘上2,3,5,7,找到当前的一个最小值。
2、按上述规律打表。也可以暴力先求出所有满足条件的值,然后直接赋值给一个数组,只是这样做代码量比较长。但是用时更短。
3、注意输出格式。序数词什么时候是st,nd,rd,什么时候是th。

代码

#include <iostream>
#include <cstring>

using namespace std;

const int MAX = 5843;
int dp[MAX];

void init(){
    dp[1] = 1;
    int a = 1;
    int b = 1;
    int c = 1;
    int d = 1;
    for(int i=2; i<MAX; i++){
        dp[i] = min(dp[a]*2, min(dp[b]*3, min(dp[c]*5, dp[d]*7)));
        if(dp[i]==dp[a]*2){
            a++;
        }
        if(dp[i]==dp[b]*3){
            b++;
        }
        if(dp[i]==dp[c]*5){
            c++;
        }
        if(dp[i]==dp[d]*7){
            d++;
        }
    }
}

int main() {
    
    memset(dp, 0, sizeof(dp));
    init();
    
    int n;
    scanf("%d", &n);
    while(n){
        printf("The %d", n);
        if(n%100>=11 && n%100<=13){
            printf("th ");
        }
        else if(n%10==1){
            printf("st ");
        }
        else if(n%10==2){
            printf("nd ");
        }
        else if(n%10==3){
            printf("rd ");
        }
        else{
            printf("th ");
        }
        printf("humble number is %d.\n", dp[n]);
        scanf("%d", &n);
    }

    return 0;
}

结果

【简单动态规划dp+打表+输出格式】HDU-1058 Humble Numbers