Pintant cares

(Us recomanem resoldre aquest problema en C++.)

Al Litus i a l’Esomer els agrada pintar la cara als rivals en els
concursos de programació, i tant és així que han decidit fer-ho
literalment. En Litus ha triat una cadena d’n colors
s = s₁, s₂, …, s_(n), i ara l’Esomer haurà de pintar n cares amb els
colors codificats dins d’s.

Cada pintada consisteix a escollir un color c i dos índexs
1 ≤ e ≤ d ≤ n, i pintar de color c totes les cares de l’interval [e, d].
Les cares es poden repintar diverses vegades, i el color nou sempre
sobreescriu l’anterior.

Quin és el mínim nombre de pintades que ha de fer l’Esomer perquè al
final les n cares acabin amb els colors objectiu?

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i s. Podeu
suposar 1 ≤ n ≤ 200, que els caràcters dintre d’s són lletres i dígits,
i que no hi ha dos caràcters consecutius iguals.

Sortida

Per a cada cas, escriviu el cost mínim de pintar totes les cares.

Puntuació

- Cas A:

  Casos on 1 ≤ n ≤ 100 i cada paraula conté quatre símbols diferents com
  a màxim.

- Cas B:

  Casos de tot tipus.

Informació del problema

Autoria: Jan Matas

Generació: 2026-02-28T13:58:47.109Z

© Jutge.org, 2006–2026.
https://jutge.org
