Problem
Chloé a récemment installé Zuma sur son téléphone. Le joueur reçoit une rangée de n gemmes, dont la i-ième a la couleur c
i. Le but du jeu — détruisez toutes les pierres en aussi peu de secondes que possible.
En une seconde, Chloé peut choisir n'importe quelle sous-chaîne (une séquence de pierres adjacentes) qui est un palindrome et la supprimer. Après avoir retiré cette sous-chaîne, les pierres restantes sont déplacées pour former à nouveau une rangée continue. Quel est le nombre minimum de secondes nécessaires pour détruire toute la ligne ?
Rappelons qu'une chaîne (ou sous-chaîne) est un palindrome si elle se lit de la même manière de gauche à droite que de droite à gauche. Dans ce cas, cela signifie que la couleur de la première pierre est égale à la couleur de la dernière pierre, la couleur de la seconde est égale à la couleur de l'avant-dernière, et ainsi de suite.
Saisie :
La première ligne de l'entrée contient un seul entier n (1 ≤ n ≤ 500) — le nombre de pierres dans la rangée initiale.
La deuxième ligne contient n entiers, dont le i-ème est égal à c
i (1 ≤ c
i ≤ n) &mdash ; la couleur de la ième pierre de la rangée initiale.
Sortie :
Imprimer un seul entier — le nombre minimum de secondes nécessaires pour supprimer toutes les gemmes.
Exemples :
| Entrée |
Sortie |
3
1 2 1
| 1 |
3
1 2 3
| 3 |
7
1 4 4 2 3 2 1
| 2 |
Explications :
La séquence dans le troisième exemple est [1, 4, 4, 2, 3, 2, 1] -> [1, 4, 4, 1] -> ; []