首页 > ACM题库 > HDU-杭电 > HDU 3199-Hamming Problem-动态规划-[解题报告]HOJ
2014
03-06

HDU 3199-Hamming Problem-动态规划-[解题报告]HOJ

Hamming Problem

问题描述 :

For each three prime numbers p1, p2 and p3, let’s define Hamming sequence Hi(p1, p2, p3), i=1, … as containing in increasing order all the natural numbers whose only prime divisors are p1, p2 or p3.

For example, H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, …

So H5(2, 3, 5)=6.

输入:

In the single line of input file there are space-separated integers p1 p2 p3 i.

输出:

In the single line of input file there are space-separated integers p1 p2 p3 i.

样例输入:

7 13 19 100

样例输出:

26590291

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1058(1058)

              http://acm.hdu.edu.cn/showproblem.php?pid=3199 (3199)

题目大意:给你四个素数2,3,5,7,只由它们四个组成合数,对这些合数从大到小进行排列,求第n个合数的大小。

解题思路:

          一看到这题,开始想要暴力,从1到Max进行横扫遍历,ok这题暴力没问题1171ms,因为题目给了限制n最大只有5842,如果我给的数很大呢,比如n=100000,暴力明显TLE。

          所以这题我们要换种思路,因为题目只给了4个数(如果题目没给素数排好序,则应该先排序),所以答案必由这四个数组成,我们记这个数的组成方式为2^a*3^b*5^c*7^d,比如1为0000,630为1211,即2*3*3*5*7. 所以我们可以用a,b,c,d分别记录2,3,5,7出现的次数,这样做的好处就是可以利用前面计算的结果按顺序推出后面的结果,如果你对过程还不是很熟悉,列几个先试试。

      小提醒:1.遇见这样的字母输出千万要注意观察规律,藐视我看了很久。

                 2.不确定大小的数最好用__int64代替int。

                 3.题目给的素数已经确定,可以选择打表,效率提高很多。 

                 4.千万要淡定,一种方式行不通可以考虑其他方法,藐视我开始是胡搞中间总是少几个数,果然换一种写法。

 

1058:

#include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 using namespace std;
 
 const int maxn=5843;
 __int64  f[maxn];
 
 __int64 Min(__int64 a, __int64 b, __int64 c,__int64 d)
 {
     a=min(a,b);
     a=min(a,c);
     a=min(a,d);
     return a;
 }
 
 int main()
 {
     f[0]=1;
     int a=0, b=0, c=0, d=0;
     for(int i=1; i<maxn; i++)  //打表
     {
         f[i]=Min(f[a]*2,f[b]*3,f[c]*5,f[d]*7);   //这里我们用到一点动态规划思想,每次只取前面记录的最小值,依次类推
         if(f[i]==f[a]*2) a++;  //2出现的次数
         if(f[i]==f[b]*3) b++;  //3出现的次数
         if(f[i]==f[c]*5) c++;  //5出现的次数
         if(f[i]==f[d]*7) d++;  //7出现的次数
     }
     int  n;
     while(~scanf("%d",&n),n)
     {
         if(n%100==11||n%100==12||n%100==13)
             printf("The %dth humble number is %I64d.\n",n,f[n-1]);
         else
         {
             if(n%10==1)
                 printf("The %dst humble number is %I64d.\n",n,f[n-1]);
             else if(n%10==2)
                 printf("The %dnd humble number is %I64d.\n",n,f[n-1]);
             else if(n%10==3)
                 printf("The %drd humble number is %I64d.\n",n,f[n-1]);
             else
                 printf("The %dth humble number is %I64d.\n",n,f[n-1]);
         }
     }
     return 0;
 }

 

3199(记得给素数先排序):

#include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 using namespace std;
 
 const int maxn=1000001;
 __int64  f[maxn];
 
 __int64 Min(__int64 a, __int64 b, __int64 c)
 {
     a=min(a,b);
     a=min(a,c);
     return a;
 }
 
 int main()
 {
     __int64  s[3], n, a, b, c;
     while(scanf("%I64d%I64d%I64d%I64d",&s[0],&s[1],&s[2],&n)!=EOF)
     {
         sort(s,s+3);
         f[0]=1;
         a=b=c=0;
         for(int i=1; i<=n; i++)
         {
             f[i]=Min(f[a]*s[0],f[b]*s[1],f[c]*s[2]);
             if(f[i]==f[a]*s[0]) a++;
             if(f[i]==f[b]*s[1]) b++;
             if(f[i]==f[c]*s[2]) c++;
         }
         printf("%I64d\n",f[n]);
     }
     return 0;
 }

 

 

           

参考:http://www.cnblogs.com/kane0526/archive/2012/11/14/2769198.html


  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  2. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了