Votre poste de travail est situé à la sortie de la chaîne de production des flip-flaps. Vous recevez d'un côté les flip-flaps en attente de peinture, chacune devant être peinte d'une couleur donnée. De l'autre côté, vous disposez de C pots de peinture, un de chaque couleur. Votre désopilante tâche consiste à peindre chaque jouet avec la couleur adéquate.
Peindre une flip-flap est facile si le pot de peinture correspondant est déjà ouvert. Toutefois, si ce n'est pas le cas, vous devez mettre la main sur votre tournevis pour retirer le couvercle avant de peindre. De plus, la politique de l'entreprise vous interdit d'avoir plus de K pots de peinture ouverts simultanément, un excès de vapeurs de peinture pouvant susciter de sérieuses hallucinations. Ainsi, à partir du moment où vous avez exactement K pots ouverts, vous devez fermer l'un d'eux avant de pouvoir en ouvrir un autre. Tous les pots sont initialement fermés.
L'ouverture d'un pot étant une tâche fastidieuse, vous cherchez à en réaliser le moins possible. Étant données les couleurs des différentes flip-flaps et l'ordre dans lequel vous devez les peindre, votre objectif est de trouver le nombre minimal d'ouvertures de pots que vous aurez à effectuer pour peindre toutes les flip-flaps de la bonne couleur.
Les N lignes suivantes décrivent la couleur de chaque flip-flap, dans l'ordre dans lequel vous devez les peindre. Chaque ligne contiendra un entier ci correspondant à la couleur de la ie flip-flap à peindre (1 <= ci <= C).
entrée :
10 4 2 3 4 2 2 3 4 1 4 3 4
sortie :
6
Couleur | Pots ouverts | Action effectuée |
3 | 3 | Ouverture du pot 3. |
4 | 3, 4 | Ouverture du pot 4. |
2 | 2, 3 | Fermeture du pot 4, ouverture du pot 2. |
2 | 2, 3 | |
3 | 2, 3 | |
4 | 3, 4 | Fermeture du pot 2, ouverture du pot 4. |
1 | 1, 4 | Fermeture du pot 3, ouverture du pot 1. |
4 | 1, 4 | |
3 | 3, 4 | Fermeture du pot 1, ouverture du pot 3. |
4 | 3, 4 |
Cette suite nécessite six ouvertures de pots différentes, ce qui correspond au
minimum réalisable.