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_1, s_2, \ldots, 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 \le e \le d \le 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 \le n \le 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 \le n \le 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