POJ1338Ugly Numbers（DP）

第一反应就是DP，DP[i] = min{2*DP[j], 3*DP[k], 5*DP[p] j,k,p<i};于是枚举一下0～i－1即可

后来听到室友说，可以通过上一个×2、×3、×5得到。于是搞了个优先队列预处理。

后来看了一下以前A的代码。O(n)的。。。（虽然不是我自己做出的＝＝）

时间都是0Ms

O(n^2)和O(nlogn)的：

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define MAX(a,b) (a > b ? a : b)
17 #define MIN(a,b) (a < b ? a : b)
18 #define mem0(a) memset(a,0,sizeof(a))
19 
20 typedef long long LL;
21 const double eps = 1e-12;
22 const int MAXN = 1005;
23 const int MAXM = 5005;
24 
25 struct NODE
26 {
27     int num;
28     int flag;
29     NODE(){}
30     NODE(int _num, int _flag){num=_num;flag=_flag;}
31     bool operator < (NODE B)const
32     {
33         return num > B.num;
34     }
35 };
36 int DP[1610], N;
37 
38 //void init()
39 //{
40 //    int time = 0;
41 //    for(int i=1;i<=1500;i++) DP[i] = INF;
42 //    DP[1] = 1;  int now = 1;
43 //    int two=1, three=1, five=1;
44 //    for(int i=2;i<=1500;i++)
45 //    {
46 //        for(int j=min(two,min(three,five));j<i;j++)
47 //        {
48 //            time ++;
49 //            if(DP[j]*2 > now && DP[i]>DP[j]*2){ DP[i] = min(DP[i], DP[j]*2); two = j;break;}
50 //            if(DP[j]*3 > now && DP[i]>DP[j]*3){ DP[i] = min(DP[i], DP[j]*3); three = j;}
51 //            if(DP[j]*5 > now && DP[i]>DP[j]*5){ DP[i] = min(DP[i], DP[j]*5); five = j;}
52 //        }
53 //        now = DP[i];
54 //    }
55 //    //printf("Time=%d
", time);
56 //}
57 
58 void init()
59 {
60     priority_queue<NODE>q;
61     NODE U;  U.num=1; U.flag=-1;
62     q.push(U);
63     int num = 1, tot = 1;
64     while(1)
65     {
66         U = q.top(); q.pop();
67         DP[num++] = U.num;
68         if(num>1500) return ;
69         if(tot > 1600) continue;
70         q.push(NODE(U.num*5, 1));                  tot++;
71         if(U.flag<=0) {q.push(NODE(U.num*3, 0));   tot++; }
72         if(U.flag<=-1){q.push(NODE(U.num*2, -1));  tot++; }
73     }
74 }
75 
76 int main()
77 {
78    // printf("%d
", (int)(1600 * (log(1600.0)/log(2.0))));
79    // freopen("test.in", "r", stdin);
80     init();
81     while(~scanf("%d", &N) &&N)
82     {
83         printf("%d
", DP[N]);
84     }
85     return 0;
86 }

O(n)的：不是我写的＝＝

 1 #include <stdio.h>
 2 int min(int a,int b,int c)
 3 {
 4     if(b<a)
 5     a=b;
 6     if(c<a)
 7     a=c;
 8     return a;
 9 }
10 int main()
11 {
12     int n;
13     int i2_mul;
14     int i3_mul;
15     int i5_mul;
16     unsigned long ugly[1501];
17 
18     i2_mul = 1;
19     i3_mul = 1;
20     i5_mul = 1;
21     ugly[1]=1;
22 
23     for(  int i = 2; i <= 1500; i++ )
24     {
25         ugly[i] = min(ugly[i2_mul]*2,ugly[i3_mul]*3,ugly[i5_mul]*5);
26         if(ugly[i] == ugly[i2_mul]*2 )
27             i2_mul++;
28         if(ugly[i] == ugly[i3_mul]*3 )
29             i3_mul++;
30         if(ugly[i] == ugly[i5_mul]*5)
31             i5_mul++;
32     
33     }
34 
35 
36     while(true)
37     {
38         scanf("%d",&n);
39 
40         if( n == 0 )
41             break;
42 
43         printf("%d
",ugly[n]);
44 
45     }
46 
47     return 0;
48 }

POJ1338Ugly Numbers（DP）

相关推荐