HDU 1058 Humble Numbers (DP)

1311 ワード

考え方:
2,3,5,7の4つの数でHumble Numbersを構築した.
dp[]配列で格納される数については、事前に表を打つ.
ACコード:
#include<stdio.h>
int dp[5843];
int n;
int Min(int a,int b,int c,int d)
{
	if(a<=b&&a<=c&&a<=d)return a;
	else if(b<=a&&b<=c&&b<=d)return b;
	else if(c<=a&&c<=b&&c<=d)return c;
	else return d;
}
int main()
{
	int i;
	int t2,t3,t5,t7;
	int t;
	dp[1]=1;
	t2=t3=t5=t7=1;
    for(i=2;i<=5842;i++)
	{
	   t=Min(2*dp[t2],3*dp[t3],5*dp[t5],7*dp[t7]);
	   if(t==2*dp[t2])t2++;
	   if(t==3*dp[t3])t3++;
	   if(t==5*dp[t5])t5++;
	   if(t==7*dp[t7])t7++;
	   dp[i]=t;
	}
    while(scanf("%d",&n)!=-1&&n)
	{
         if(n%10==1&&n%100!=11)printf("The %dst humble number is %d.
",n,dp[n]); else if(n%10==2&&n%100!=12)printf("The %dnd humble number is %d.
",n,dp[n]); else if(n%10==3&&n%100!=13)printf("The %drd humble number is %d.
",n,dp[n]); else printf("The %dth humble number is %d.
",n,dp[n]); } return 0; }