Indian Computing Olympiad

Dynamic Programming→Yertle the Turtle

Yertle, the turtle king, has 5607 turtles. He wants to stack up these turtles to form a throne. Each turtle i has weight W[i] and capacity C[i]. A turtle can carry on its back a stack of turtles whose total weight is within C[i]. This should include W[i], the weight of the current turtle, so assume that C[i]≥W[i] always.

Find the height of the tallest turtle throne that Yertle can build.

Solution