UVa 231

From Algorithmist
Jump to navigation Jump to search

231 - Testing the Catcher[edit]



Summary of the problem statement goes here.


This problem is based in the idea of selecting a sequence of non decreasing integer elements from an array in such a way that its length is maximised.

An algorithm is fast enough for the problem to be accepted.

A dynamic programming method can be used if executed as described below:

Let be the height of the missile (i) The missile 0 is at height infinity. Let be the interception count after i missiles have been faced by the catcher. Notice that = 0.

Then can be calculated as the maximum of the elements of V indexed from 0 to i whose height is smaller than or equal to the height added of 1 (the current interception).

That way, if 5 missiles at heights 5 10 9 7 16 face the catcher, the arrays can be defined as follows:

H = infinity 5 10 9 7 16

V = 0 1 1 2 3 1

To extract the result, get the largest element of V.

--Schultz 15:32, 10 Oct 2006 (EDT)