Bulbs
Time limit1sMemory limit128 MB
Given N colored bulbs where changing one bulb also flips its contiguous same-colored neighbors, find the minimum number of changes to make all bulbs one color (classic zuma-like merging interval DP).
- Level
Medium6 of 10
- Topics
- Dynamic programming, Array
- Solved
- No attempts yet
Problem
There are N bulbs connected in a row. Each bulb can display one of at most K colors. The number inside each circle represents the bulb's color.
Each bulb has a switch, so you may change that bulb to any color. When you change a bulb's color, every bulb connected to it on the left or right that had the same color before the change also changes. This continues until a bulb of a different color is reached.
For example, in the picture above, if bulb 4 is changed to color 2, bulbs 5 and 6 also change to color 2 because they were connected to bulb 4 with the same color. As a result, bulbs 4, 5, and 6 all become color 2, as shown below.
Given N and the initial colors of the bulbs, find the minimum number of color changes needed to make all bulbs have one identical color. Each color is represented by an integer from 1 to K.
Input
The first line contains two positive integers N and K: the number of bulbs and the number of colors the bulbs can display. N is an integer from 1 to 200, and K is an integer from 1 to 20.
The second line contains N integers, separated by spaces, giving the colors of the bulbs in bulb-number order.
Output
Print one integer: the minimum number of bulb color changes needed until all bulbs have the same color.