【简单动态规划dp+打表+输出格式】HDU-1058 Humble Numbers
程序员文章站
2024-01-23 23:25:10
...
注解
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;
}
结果
上一篇: css3实现超好看的旋转动画
下一篇: PHP十天快速入门等收集资料