UVa 231

From Algorithmist
Jump to navigation Jump to search

231 - Testing the Catcher[edit]

ACM UVA 231

Summary[edit]

Summary of the problem statement goes here.

Explanation[edit]

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)

Solutions[edit]