Problem
Chloe instaló recientemente a Zuma en su teléfono. El jugador recibe una fila de n gemas, la i-ésima de las cuales tiene el color c
i. El propósito del juego — destruye todas las piedras en el menor tiempo posible.
En un segundo, Chloe puede elegir cualquier subcadena (una secuencia de piedras adyacentes) que sea un palíndromo y eliminarla. Después de eliminar esta subcadena, las piedras restantes se desplazan para formar una fila continua nuevamente. ¿Cuál es el número mínimo de segundos necesarios para destruir toda la línea?
Recuerde que una cadena (o subcadena) es un palíndromo si se lee igual de izquierda a derecha que de derecha a izquierda. En este caso, esto significa que el color de la primera piedra es igual al color de la última piedra, el color de la segunda es igual al color de la penúltima y así sucesivamente.
Entrada:
La primera línea de la entrada contiene un único número entero n (1 ≤ n ≤ 500) — el número de piedras en la fila inicial.
La segunda línea contiene n enteros, el i-ésimo de los cuales es igual a c
i (1 ≤ c
i ≤ n) &mdash ; el color de la i-ésima piedra en la fila inicial.
Salida:
Imprime un solo entero — el número mínimo de segundos necesarios para eliminar todas las gemas.
Ejemplos:
| Entrada |
Salida |
3
1 2 1
| 1 |
3
1 2 3
| 3 |
7
1 4 4 2 3 2 1
| 2 |
Explicaciones:
La secuencia del tercer ejemplo es [1, 4, 4, 2, 3, 2, 1] -> [1, 4, 4, 1] -> []