【HDU 1058&HDU 3199類似丑数】単純DP思想

テーマリンク：http://acm.hdu.edu.cn/showproblem.php?pid=1058（1058）
               http://acm.hdu.edu.cn/showproblem.php?pid=3199 （3199）
4つの素数を2,3,5,7としてあげます。それらの4つだけからなる合数です。これらの合数は大きいから小さいまで並べて、n番目の合数の大きさを求めます。
問題解決の考え方：
          この問題を見ると、暴力を始めたいと思います。1からMaxまで横断的にスキャンしています。okこの暴力は大丈夫です。1171 msです。制限nを与えましたので、最大5842しかありません。もし私が与えた数が大きいなら、例えばn=100000、暴力は明らかにTLEです。
          ですから、この問題は4つの数字しかあげられません。だから、答えは必ずこの4つの数からなります。この数の構成は2^a*3^b*5^c*7^dです。たとえば、1は0000で、630は1211で、つまり2*3*5*7です。だから、私たちはa、5 d、それぞれの記録ができます。このようにするメリットは前の計算結果を利用して順番に後の結果を出すことができます。もしあなたがまだ過程に慣れていないなら、いくつかの列を作ってみてください。
      小さい注意：1.このような字母の出力に出会ってくれぐれも規則を観察することに注意して、私を軽視して長い間見ました。
                 2.大きさが不確定な数は_u uを使うのが一番いいです。intの代わりにint 64
                 3.題名の与えられた素数はすでに決まっています。メーターを選択することができます。効率がよくなります。 
                 4.落ち着いてください。一つの方法が通じなくて、他の方法を考えてもいいです。私を蔑視し始めたのはでたらめな中間で、いつも少なくて、やはり書き換えます。
 
1058:

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <algorithm>

 4 #include <cstring>

 5 using namespace std;

 6 

 7 const int maxn=5843;

 8 __int64  f[maxn];

 9 

10 __int64 Min(__int64 a, __int64 b, __int64 c,__int64 d)

11 {

12     a=min(a,b);

13     a=min(a,c);

14     a=min(a,d);

15     return a;

16 }

17 

18 int main()

19 {

20     f[0]=1;

21     int a=0, b=0, c=0, d=0;

22     for(int i=1; i<maxn; i++)  //  

23     {

24         f[i]=Min(f[a]*2,f[b]*3,f[c]*5,f[d]*7);   //              ，            ，    

25         if(f[i]==f[a]*2) a++;  //2     

26         if(f[i]==f[b]*3) b++;  //3     

27         if(f[i]==f[c]*5) c++;  //5     

28         if(f[i]==f[d]*7) d++;  //7     

29     }

30     int  n;

31     while(~scanf("%d",&n),n)

32     {

33         if(n%100==11||n%100==12||n%100==13)

34             printf("The %dth humble number is %I64d.
",n,f[n-1]);

35         else

36         {

37             if(n%10==1)

38                 printf("The %dst humble number is %I64d.
",n,f[n-1]);

39             else if(n%10==2)

40                 printf("The %dnd humble number is %I64d.
",n,f[n-1]);

41             else if(n%10==3)

42                 printf("The %drd humble number is %I64d.
",n,f[n-1]);

43             else

44                 printf("The %dth humble number is %I64d.
",n,f[n-1]);

45         }

46     }

47     return 0;

48 }

 
3199(素数の優先順位を覚えています):

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <algorithm>

 4 #include <cstring>

 5 using namespace std;

 6 

 7 const int maxn=1000001;

 8 __int64  f[maxn];

 9 

10 __int64 Min(__int64 a, __int64 b, __int64 c)

11 {

12     a=min(a,b);

13     a=min(a,c);

14     return a;

15 }

16 

17 int main()

18 {

19     __int64  s[3], n, a, b, c;

20     while(scanf("%I64d%I64d%I64d%I64d",&s[0],&s[1],&s[2],&n)!=EOF)

21     {

22         sort(s,s+3);

23         f[0]=1;

24         a=b=c=0;

25         for(int i=1; i<=n; i++)

26         {

27             f[i]=Min(f[a]*s[0],f[b]*s[1],f[c]*s[2]);

28             if(f[i]==f[a]*s[0]) a++;

29             if(f[i]==f[b]*s[1]) b++;

30             if(f[i]==f[c]*s[2]) c++;

31         }

32         printf("%I64d
",f[n]);

33     }

34     return 0;

35 }