LineColoring
TCO 2018 Fun 2B · 2018-04-20 · by lg5293
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
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.
Constraints
- x will have between 1 and 1,000 elements, inclusive.
- Each element of x will be between 1 and 10^6, inclusive.
{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
Submissions are judged against all 152 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LineColoring with a public method int minCost(vector<int> x) · 152 test cases · 2 s / 256 MB per case