Module: Patterns in Dynamic Programming - 2


Problem

1 /5


fill game

Theory Click to read/hide

Disclaimer: The method described below is not universal, but it can often solve a problem or help you come to the right solution.

If a problem asks you to optimally destroy/collapse/merge (or similar) an array, then you should try to solve it using dynamic programming on subsegments.

Let's get dp[l][r] - the optimal answer for a subsegment with indices from l to r. Recalculation of dynamics is highly task dependent, but there are the following general ideas:

1) Look at the extreme elements l and r. If they match or complement in some other way, then most likely it will be possible to update the value of dp[l][r] via dp[l+1][r-1]. Otherwise via dp[l][r-1] or dp[l+1[r].

2) It often happens that the segment [l;r] cannot be represented through a single construction. Then it is necessary to consider all possible sections of this subsegment into two parts, that is, iterate over the element k from l to r-1 and recalculate dp[l][r] through dp[l][k] and dp[k+1][r] . In smaller subsegments, these sections were also sorted out, therefore, in fact, the options for splitting the subsegment [l;r] not only into two parts, but into any number of them are taken into account.
 

Problem

You are given a strip of checkered paper made of n colored squares numbered from 1 to n from left to right. The i-th square is initially colored ci.

We say that squares i and j lie in the same component if ci = cj and ci = ck for all k satisfying i < k < j. In other words, all squares on the segment from i to j must have the same color.
For example, the strip [3,3,3] has 1 connected component, while [5,2,4,4] has 3.

Fill game is played on this strip as follows:
At the beginning of the game, you choose one random starting square (this does not count as a turn).
Then, on each move, you change the color of the connected component containing the starting square to any other color.

Find out the minimum number of moves needed to recolor the entire strip in one color.

Input:
The first line contains a single integer n (1 ≤ n ≤ 5000) — number of squares.

The second line contains the integers c1,c2,…,cn (1 ≤ ci <5000) — the initial colors of the squares.

Output:
Print a single integer — the minimum number of moves to make.

Examples:
 
Input Output
4
5 2 2 1 		2
8
4 5 2 2 1 3 5 5 		4
1
4		 0

Explanation:
One of the optimal ways in the first example: [5, 2, 2, 1] -> [5, 2, 2, 2] -> [5, 5, 5, 5]

time 2000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!