Pintant cares P34492

(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.