Algoritmusok
Almák és banánok helyett egyszerűbb lesz úgy leírni a megoldásokat, mintha festenénk, "A" és "B" színnel.
0. ötlet - hibás, de javítható (Erben Péter)
Ha az utolsó karakterek egyeznek, akkor egy 1-gyel kisebb feladatot kell megoldani. Ha különböznek, akkor aszerint ágazhat el a rekurzió, hogy az utolsó karaktert átfestő lépés hol kezdődik. (A kezdete előtti rész optimumát a rekurzió kiszámítja.)
1. ötlet (Choung Do)
A következő segédtáblázatot vezessük be:
festésiköltség[200,200,2]
Itt
festésiköltség[i,j,s] azt jelenti, hogy legkevesebb hány ecsetvonással
készíthető el az
[i..j] rész, ha első lépésként a teljes intervallumot
s színnel festettük le. Ez a segédtáblázat lineáris lépésszámú algoritmussal előállítható, hiszen ha a teljes intervallumot lefestettük az
s színnel, akkor az optimális megoldás ezután az
1-s színű "szigeteket" festi meg, ezek pedig az intervallum végigolvasása során meghatározhatók.
Belátható, hogy a 0. ötletben felvetett módszer javított változata már helyes: továbbra is aszerint ágazunk el, hogy az utolsó karaktert átfestő lépés hol kezdődik, de úgy képzeljük, hogy itt egy a festésiköltség tömbben kiszámolt lépésszámú műveletet végeztünk.
2. ötlet (Jeffrey Wang)
Ez lesz a klasszikus dinamikus programozási megoldás.
A dp(i,j,típus) rekurzív függvény kiszámítását fogjuk táblázatolással gyorsítani.
A típus lehet 0, 1 vagy 2, ahol 0 és 1 rendre az "A", "B" színeket, 2 pedig azt jelöli, hogy még nem festettünk. A függvény azt adja meg, hogy mennyi az [i..j] szakasz elkészítésének költsége, ha első lépésként a típusban jelölt színnel az egészet végigfestettük (illetve ha típus=2, akkor nem csináltunk még semmit).
Ha a sorozatok hossza n, akkor (Pascalos indexelést használva), a dp(1,n,2) hívás adja a feladat megoldását.
3. ötlet (Uray János)
Az F[2] tömb tárolja a legutolsó A és B festések végeit (A = 0, B = 1)
In: Ha a legutóbbi A-sor (0) vagy a legutóbbi B-sor (1) teljesen a
másikon belül van. Ha nem volt ilyen, akkor -1.
Kódok
