Saturday, September 5, 2009

FlowerGarden - 2004 TCCC Round 1 - TopCoder

Dynamic Programming

I first figure out for each flower how many flowers and which flowers have to go first.
It's not difficult to do that. I implemented arr[50][50] if arr[i][j] is true then flower j must go first before flower i. When arr[i][j] is true??? If height[i] > height[j] && inter( bloom[i], wilt[i], bloom[j], wilt[j] ) then arr[i][j] = true
The function "inter" determines whether the time of bloom and wilt for flower i and j have conflict.
After calculating "arr" I start finding the highest flower that doesn't conflict with others and push it back to the output vector and manipulate "arr" after choosing a flower, I mean if arr[i][chosen] == 1 then arr[i][chosen] = 0 and repeat this procedure n times to choose n flowers.

No comments:

Post a Comment