Problem Statement
????
A group of vertical blocks are placed densely one after another on the ground. The blocks each have a width of 1, but their heights may vary. For example, if the heights of the vertical blocks are given as {1,5,5,1,6,1}, the configuration would look like the following picture:
×
×× ×
×× ×
×× ×
×× ×
××××××
Your task is to reproduce the exact shape of this structure using some number of non-intersecting rectangles. You will be given a int[] heights representing the heights of the vertical blocks from left to right. Return the minimal number of rectangles necessary to perform this task with the given configuration of blocks.
Definition
????
Class:
BlockStructure
Method:
cover
Parameters:
int[]
Returns:
int
Method signature:
int cover(int[] heights)
(be sure your method is public)
????
Constraints
-
heights will have between 1 and 50 elements, inclusive.
-
Each element of heights will be between 1 and 1000, inclusive.
Examples
0)
????
{1,5,5,1,6,1}
Returns: 3
We can use rectangles with sizes 6x1, 2x4 and 1x5.
×
×× ×
×× ×
×× ×
×× ×
××××××
1)
????
{2,2,2,4,4}
Returns: 2
We can use a 3x2 rectangle and a 2x4 rectangle.
××
××
×××××
×××××
2)
????
{6,6,6,6,6,6}
Returns: 1
The structure is a rectangle.
3)
××××××
××××××
××××××
××××××
××××××
××××××
????
{71,44,95,16,10,80,12,17,98,61}
Returns: 10
It's impossible to use less than 10 rectangles.
4)
????
{100,100,97,100,100,100,97,98,99,99}
Returns: 5
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.