Van egy nyakláncunk, ami N gyöngyből áll, ezek fehérek, pirosak vagy kékek (3<=N<=350), véletlenszerű elrendezésben.
Itt látható két példa N = 29-re:.
1 2 1 2
r b b r b r r b
r b b b
r r b r
r r w r
b r w w
b b r r
b b b b
b b r b
r r b r
b r r r
b r r r
r r r b
r b r r r w
r piros gyöngy
b kék gyöngy
w fehér gyöngy
Az első és második gyöngy az ábrán meg lett jelölve. Az első ábrán lévő nyaklánc csak kék és piros gyöngyökből áll, és leírható a következő 'b'-kből és 'r'-ekből álló karakterlánccal (ha a 3. gyöngynél kezdjük a leírást):
br
brrrbbbrrrrrbrrbbrbbbbrrrrb
A nyaklánc egy helyen elszakítható és kiteríthető egyenesen. Ezután mindkét végéről levehetők gyöngyök a következő módon: elindulunk a lánc végén, és addig szedjük le a gyöngyöket, amíg az elsővel azonos színűek. Ezt ismételjük a másik végén is, de ezek a gyöngyök eltérhetnek színben az előbb leszedettektől (egymástól viszont nem).
Feladat
Írjunk programot, ami megadja, hol kell elszakítani a nyakláncot ahhoz, hogy a lehető legtöbb gyöngyöt tudjuk összeszedni.
A fenti első ábrán például 8 gyöngy gyűjthető össze, ha a 9. és 910., vagy ha a 24. és 25. gyöngy között szakítunk.
Vannak olyan nyakláncok is, amelyekben fehér gyöngyök is találhatók, m int például a fenti második ábrán. A gyöngyök gyűjtésekor ezek tekinthetők pirosnak és kéknek is. Az ilyen nyakláncok leírása az előzőhöz hasonló, de 'w' karakterek is szerepelhetnek benne, melyek a fehér gyöngyök helyét jelölik.
Bemenet
A bemenet első sora a gyöngyök N számát adja meg, a másodikban pedig N karakter található, a gyöngyök színe.
Kimenet
A begyűjthető gyöngyök maximális száma.
Példa
Bemenet |
Kimenet |
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
|
11
|
A példa magyarázata:
Képzeljül el, hogy kétszer egymás után illesztettük a nyakláncot (mintha a végén tovább lehetne haladni körben).
A nyaklánc két azonos példánya itt van összeillesztve
v
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb|wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
******|*****
rrrrrb bbbbb <-- a fehérek választása
rrrrr#bbbbbb
5 x r 6 x b <-- összesen 11
Tesztadatok
Címkék
A feladat forrása: USACO training material, Broken Necklace
Algoritmusok:
megoldás