现在的位置: 首页 > 综合 > 正文

HDU 1058 DP

2017年11月21日 ⁄ 综合 ⁄ 共 835字 ⁄ 字号 评论关闭

自己做的时候没想法。。。。好渣啊好渣怎么办!。。。。

觉得这样的题不算DP吧。。。感觉不大。就是轮流找素数因子,每次把找到最小的那个值更新,觉得方法挺巧的。说是很卡输出格式,估计还顺便考英语。。。不过有前辈助力,所以没有纠结太久 。

#include <stdio.h>
#define maxn 60000
int ar[maxn];
int min(int a,int b,int c,int d)
{
    int t1=a>b?b:a;
    int t2=c>d?d:c;
    return t1>t2?t2:t1;
}
void find()
{
    int i,a,b,c,d;
    int n1,n2,n3,n4;
    ar[1]=1;
    n1=n2=n3=n4=1;
    for(i=2;i<maxn;i++)
    {
        a=ar[n1]*2;
        b=ar[n2]*3;
        c=ar[n3]*5;
        d=ar[n4]*7;
        ar[i]=min(a,b,c,d);
        if(ar[i]==a) n1++;
        if(ar[i]==b) n2++;
        if(ar[i]==c) n3++;
        if(ar[i]==d) n4++;
    }
}
int main()
{
    int n;
    find();
    while(scanf("%d",&n),n!=0)
    {
        int i,j;
        i=n/10;
        j=i%10;
        //if(n%10==1&&j==1) printf("The %dth humble number is %d.\n",n,ar[n]);
        if(n%10==1&&j!=1) printf("The %dst humble number is %d.\n",n,ar[n]);
        else if(n%10==2&&j!=1) printf("The %dnd humble number is %d.\n",n,ar[n]);
        else if(n%10==3&&j!=1) printf("The %drd humble number is %d.\n",n,ar[n]);
        else printf("The %dth humble number is %d.\n",n,ar[n]);
    }
    return 0;
}

抱歉!评论已关闭.