Problem 4: Landscaping [Brian Dean, 2005]
Farmer John is making the difficult transition from raising mountain
goats to raising cows. His farm, while ideal for mountain goats,
is far too mountainous for cattle and thus needs to be flattened
out a bit. Since flattening is an expensive operation, he wants to
remove the smallest amount of earth possible.
The farm is long and narrow and is described in a sort of two-dimensional
profile by a single array of N (1 <= N <= 1000) integer elevations
(range 1..1,000,000) like this:
1 2 3 3 3 2 1 3 2 2 1 2,
which represents the farm's elevations in profile, depicted below
with asterisks indicating the heights:
* * * *
* * * * * * * * *
* * * * * * * * * * * *
1 2 3 3 3 2 1 3 2 2 1 2
A contiguous range of one or more equal elevations in this array
is a "peak" if both the left and right hand sides of the range are
either the boundary of the array or an element that is lower in
elevation than the peak. The example above has three peaks.
Determine the minimum volume of earth (each unit elevation reduction
counts as one unit of volume) that must be removed so that the
resulting landscape has no more than K (1 <= K <= 25) peaks. Note
well that elevations can be reduced but can never be increased.
If the example above is to be reduced to 1 peak, the optimal solution
is to remove 2 + 1 + 1 + 1 = 5 units of earth to obtain this set
of elevations:
* * * -
* * * * * - - - -
* * * * * * * * * * * *
1 2 3 3 3 2 1 1 1 1 1 1
where '-'s indicate removed earth.
PROBLEM NAME: peaks
INPUT FORMAT:
* Line 1: Two space-separated integers: N and K
* Lines 2..N+1: Each line contains a single integer elevation. Line
i+1 contains the elevation for index i.
SAMPLE INPUT (file peaks.in):
12 1
1
2
3
3
3
2
1
3
2
2
1
2
INPUT DETAILS:
This is the example used above.
OUTPUT FORMAT:
* Line 1: The minimum volume of earth that must be removed to reduce
the number of peaks to K.
SAMPLE OUTPUT (file peaks.out):
5
