LineColoring | Topcoder Archive

Problem Statement

There are n newly-built houses standing in a line. The houses haven't been painted yet. Each house has a number. The numbers are some arbitrary (not necessarily distinct) positive integers. You are given the int[] x. The elements of x are the numbers on individual houses, in order.

Your task is to paint each house using a single color. You may use as many colors as you like, with one restriction: adjacent houses cannot share the same color.

Given a coloring of all the houses, its penalty is calculated as follows:

For each color you used, look at all the houses of that color and take the maximum of their numbers.
Sum all those maxima.

Find and return the smallest possible penalty for painting all the houses.

Definition

Class:: LineColoring
Method:: minCost
Parameters:: int[]
Returns:: int
Method signature:: int minCost(int[] x)
(be sure your method is public)

Constraints

x will have between 1 and 1,000 elements, inclusive.
Each element of x will be between 1 and 10^6, inclusive.

Examples

```
{1,2,3,4,5,6,7,8,9}
```
```
Returns: 17
```
One optimal solution is to use the colors {red, blue, red, blue, red, blue, red, blue, red} in this order. The largest blue number is 8, the largest red number is 9, and their sum is 17.
```
{7,6,5,4,3,2,1}
```
```
Returns: 13
```
```
{1,2,1,2}
```
```
Returns: 3
```
```
{1,10,1,1,1,1,10}
```
```
Returns: 12
```
Here, one optimal way of painting is {blue, red, blue, green, red, green, red}. The penalty is calculated as follows: For blue houses we have max(1,1) = 1. For red houses we have max(10,1,10) = 10. For green houses we have max(1,1) = 1. Thus, the penalty is 1 + 10 + 1 = 12.

{4,5,6,7,8,9,10,11,12,13,14,15,16,17,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

Returns: 33

```
{1000000}
```
```
Returns: 1000000
```

{9450,7098,6048,1050,672,8232,5028,
672,672,42,42,42,42,42,9450,6048,
3402,3402,2688,9450,7098,6048,1050,
672,8232,5028,672,672,9450,6048,3402}

Returns: 18900

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)2024, Topcoder, Inc. All rights reserved.