Problem
Chloe recentemente instalou o Zuma em seu telefone. O jogador recebe uma linha de n gemas, a i-ésima das quais tem a cor c
i. O objetivo do jogo — destrua todas as pedras no menor tempo possível.
Em um segundo, Chloe pode escolher qualquer substring (uma sequência de pedras adjacentes) que seja um palíndromo e excluí-la. Depois de remover esta substring, as pedras restantes são deslocadas para formar uma linha contínua novamente. Qual é o número mínimo de segundos necessários para destruir toda a linha?
Lembre-se de que uma string (ou substring) é um palíndromo se for lida da esquerda para a direita da mesma forma que da direita para a esquerda. Neste caso, isso significa que a cor da primeira pedra é igual à cor da última pedra, a cor da segunda é igual à cor da penúltima e assim por diante.
Entrada:
A primeira linha da entrada contém um único inteiro n (1 ≤ n ≤ 500) — o número de pedras na linha inicial.
A segunda linha contém n inteiros, o i-ésimo dos quais é igual a c
i (1 ≤ c
i ≤ n) &mdash ; a cor da i-ésima pedra na fileira inicial.
Saída:
Imprima um único inteiro — o número mínimo de segundos necessários para remover todas as gemas.
Exemplos:
| Entrada |
Saída |
3
1 2 1
| 1 |
3
1 2 3
| 3 |
7
1 4 4 2 3 2 1
| 2 |
Explicações:
A sequência no terceiro exemplo é [1, 4, 4, 2, 3, 2, 1] -> [1, 4, 4, 1] -> []