HDU 1058 Humble Numbers【DP】

时间:2023-03-08 15:59:35
HDU 1058 Humble Numbers【DP】

题意:给出丑数的定义,只含有2,3,5,7这四个素数因子的数称为素数。求第n个丑数。

可以先观察几个丑数得出规律

1:dp[1]

2:min(1*2,1*3,1*5,1*7)

3:min(2*2,1*3,1*5,1*7)

4:min(2*2,2*3,1*5,1*7)

5:min(3*2,2*3,1*5,1*7)

6:min(3*2,2*3,2*5,1*7)

7:min(4*2,3*3,2*5,1*7)

8:min(4*2,3*3,2*5,2*7)

9:min(5*2,3*3,2*5,2*7)

然后ppt里面的方程也就好理解了

dp[i]=min(dp[p1]*2,dp[p2]*3,dp[p3]*5,dp[p4]*7)

如果选中了哪一个数,对应的伪指针移动1 注意上面的6的情况,如果有两个或两个以上的数和它相等,对应的伪指针都移动1

然后就是输出的问题了

1是first

2是second

3是third

4是fourth

----

11是eleventh

12是twelfth

13是thirteenth -----

这一题也是学习的---感觉它的转移方程有一点点不一样---用已经算出来的丑数去推出新的丑数--- 另外输出的时候看了半天(为什么要判断这么多次----5555)原来是因为序数词的后缀不一样(===5555555)

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int maxn=+; int dp[maxn]; int min(int a,int b,int c,int d)
{
a=a<b?a:b;
b=c<d?c:d;
return a<b?a:b;
} int main()
{
int n,i,p1,p2,p3,p4,dp1,dp2,dp3,dp4;
dp[]=;
p1=p2=p3=p4=;
for(i=;i<=;i++)
{
dp1=*dp[p1];
dp2=*dp[p2];
dp3=*dp[p3];
dp4=*dp[p4];
dp[i]=min(dp1,dp2,dp3,dp4);
if(dp[i]==dp1) p1++;
if(dp[i]==dp2) p2++;
if(dp[i]==dp3) p3++;
if(dp[i]==dp4) p4++;
}
while(scanf("%d",&n)!=EOF&&n)
{
if(n%==&&n%!=)
printf("The %dst humble number is %d.\n",n,dp[n]);
else if(n%==&&n%!=)
printf("The %dnd humble number is %d.\n",n,dp[n]);
else if(n%==&&n%!=)
printf("The %drd humble number is %d.\n",n,dp[n]);
else
printf("The %dth humble number is %d.\n",n,dp[n]);
}
return ;
}