POJ 1338 ugly number

#include

int u[1510];

int main()

{

int t2,t3,t5,i,p2,p3,p5;

u[1] = 1;

p2 = p3= p5 = 1;

for(i = 2;i < 1501;i ++){

t2 = u[p2] * 2;

t3 = u[p3] * 3;

t5 = u[p5] * 5;

u[i] = t2 < t3 ? (t2 < t5 ? t2 : t5) : (t3 < t5 ? t3 : t5);

if(u[i] == t2)p2 ++;

if(u[i] == t3)p3 ++;

if(u[i] == t5)p5 ++;

}

int n;

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

printf("%d\n",u[n]);

return 0;

}

开始不理解题意，RE了好几次 = =

后来想了好一阵，才搞明白算法。。。

可以用heap或者PQ来做，原理一样
相对来说，这题还有点意思 = =！！