Problem
Chloe ha recentemente installato Zuma sul suo telefono. Al giocatore viene assegnata una fila di n gemme, la i-esima delle quali ha il colore c
i. Lo scopo del gioco — distruggi tutte le pietre nel minor numero di secondi possibile.
In un secondo, Chloe può scegliere qualsiasi sottostringa (una sequenza di pietre adiacenti) che sia un palindromo ed eliminarla. Dopo aver rimosso questa sottostringa, le pietre rimanenti vengono spostate per formare nuovamente una fila continua. Qual è il numero minimo di secondi necessario per distruggere l'intera linea?
Ricordiamo che una stringa (o sottostringa) è palindromo se si legge allo stesso modo da sinistra a destra e da destra a sinistra. In questo caso, ciò significa che il colore della prima pietra è uguale al colore dell'ultima pietra, il colore della seconda è uguale al colore della penultima, e così via.
Inserimento:
La prima riga dell'input contiene un singolo numero intero n (1 ≤ n ≤ 500) — il numero di pietre nella riga iniziale.
La seconda riga contiene n numeri interi, l'i-esimo dei quali è uguale a c
i (1 ≤ c
i ≤ n) &mdash ; il colore della pietra i-esima nella riga iniziale.
Uscita:
Stampa un singolo numero intero — il numero minimo di secondi necessari per rimuovere tutte le gemme.
Esempi:
| Input |
Uscita |
3
1 2 1
| 1 |
3
1 2 3
| 3 |
7
1 4 4 2 3 2 1
| 2 |
Spiegazioni:
La sequenza nel terzo esempio è [1, 4, 4, 2, 3, 2, 1] -> [1, 4, 4, 1] -> []