Module: Padrões em Programação Dinâmica - 2


Problem

1 /5


preencher o jogo

Theory Click to read/hide

Isenção de responsabilidade: o método descrito abaixo não é universal, mas muitas vezes pode resolver um problema ou ajudá-lo a encontrar a solução certa.

Se um problema pede para você destruir/recolher/mesclar (ou similar) um array, então você deve tentar resolvê-lo usando programação dinâmica em subsegmentos.

Vamos obter dp[l][r] - a resposta ideal para um subsegmento com índices de l a r. O recálculo da dinâmica é altamente dependente da tarefa, mas existem as seguintes ideias gerais:

1) Observe os elementos extremos l e r. Se eles corresponderem ou se complementarem de alguma outra forma, provavelmente será possível atualizar o valor de dp[l][r] via dp[l+1][r-1]. Caso contrário via dp[l][r-1] ou dp[l+1[r].

2) Muitas vezes acontece que o segmento [l;r] não pode ser representado por uma única construção. Então é necessário considerar todas as seções possíveis deste subsegmento em duas partes, ou seja, iterar sobre o elemento k de l a r-1 e recalcular dp[l][r] através de dp[l][k] e dp[ k+1][r] . Em subsegmentos menores, essas seções também foram classificadas, portanto, de fato, as opções para dividir o subsegmento [l;r] não apenas em duas partes, mas em qualquer número delas são levadas em consideração.
 

Problem

Você recebe uma tira de papel xadrez feita de n quadrados coloridos numerados de 1 a n da esquerda para a direita. O i-ésimo quadrado é inicialmente colorido ci.

Dizemos que os quadrados i e j estão no mesmo componente se ci = cj e ci = ck para todo k satisfazendo i < k < j. Em outras palavras, todos os quadrados no segmento de i a j devem ter a mesma cor.
Por exemplo, a faixa [3,3,3] possui 1 componente conectado, enquanto [5,2,4,4] possui 3.

Preencher o jogo é tocada nesta faixa da seguinte forma:
No início do jogo, você escolhe um quadrado inicial aleatório (isso não conta como um turno).
Então, em cada movimento, você muda a cor do componente conectado contendo o quadrado inicial para qualquer outra cor.

Descubra o número mínimo de movimentos necessários para recolorir toda a tira de uma cor.

Entrada:
A primeira linha contém um único inteiro n (1 ≤ n ≤ 5000) — número de quadrados.

A segunda linha contém os inteiros c1,c2,…,cn (1 ≤ ci <5000) — as cores iniciais dos quadrados.

Saída:
Imprima um único inteiro — o número mínimo de movimentos a serem feitos.

Exemplos:
 
Entrada Saída
4
5 2 2 1 		2
8
4 5 2 2 1 3 5 5 		4
1
4		 0

Explicação:
Uma das formas ideais no primeiro exemplo: [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!