Courses

Programación dinámica

Patrones en Programación Dinámica - 2

Module: Patrones en Programación Dinámica - 2

Problem

1 /5

juego de relleno

Theory Click to read/hide

Descargo de responsabilidad: el método que se describe a continuación no es universal, pero a menudo puede resolver un problema o ayudarlo a encontrar la solución correcta.

Si un problema le pide que destruya/colapse/fusione (o similar) de manera óptima una matriz, entonces debe intentar resolverlo usando programación dinámica en subsegmentos.

Obtengamos dp[l][r] - la respuesta óptima para un subsegmento con índices de l a r. El recálculo de la dinámica depende en gran medida de la tarea, pero existen las siguientes ideas generales:

1) Mira los elementos extremos l y r. Si coinciden o se complementan de alguna otra manera, lo más probable es que sea posible actualizar el valor de dp[l][r] a través de dp[l+1][r-1]. De lo contrario, a través de dp[l][r-1] o dp[l+1[r].

2) A menudo sucede que el segmento [l;r] no se puede representar a través de una sola construcción. Entonces es necesario considerar todas las secciones posibles de este subsegmento en dos partes, es decir, iterar sobre el elemento k de l a r-1 y recalcular dp[l][r] hasta dp[l][k] y dp[ k+1][r] . En subsegmentos más pequeños, estas secciones también se clasificaron, por lo que, de hecho, se tienen en cuenta las opciones para dividir el subsegmento [l;r] no solo en dos partes, sino en cualquier número de ellas.

Problem

Te dan una tira de papel cuadriculado hecha de n cuadrados de colores numerados del 1 al n de izquierda a derecha. El cuadrado i-ésimo está inicialmente coloreado como c_i.

Decimos que los cuadrados i y j pertenecen a la misma componente si c_i= c_j y c_i= c_k para todos los k que satisfacen i < k < j. En otras palabras, todos los cuadrados en el segmento de i a j deben tener el mismo color.
Por ejemplo, la tira [3,3,3] tiene 1 componente conectado, mientras que [5,2,4,4] tiene 3.

juego de relleno se juega en esta franja de la siguiente manera:
Al comienzo del juego, eliges una casilla de inicio al azar (esto no cuenta como un turno).
Luego, en cada movimiento, cambia el color del componente conectado que contiene el cuadrado inicial a cualquier otro color.

Averigüe el número mínimo de movimientos necesarios para volver a colorear toda la tira en un solo color.

Entrada:
La primera línea contiene un solo número entero n (1 ≤ n ≤ 5000) — número de cuadrados.

La segunda línea contiene los enteros c₁,c₂,…,c_n (1 ≤ c_i <5000) — los colores iniciales de los cuadrados.

Salida:
Imprime un solo entero — el número mínimo de movimientos a realizar.

Ejemplos:

Explicación:
Una de las formas óptimas en el primer ejemplo: [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