Olimpiade Sains Provinsi (OSP) 2016 - Komputer, Nomor 5

Dengan Dynamic Programming,

Misalkan melati=a, mawar=b, anggrek=c

Misalkan F(N, ab) adalah banyaknya cara menyusun N pot bunga (sesuai aturan) dimana dua bunga di depannya adalah ab
Berdasarkan kesimetrian, apapun dua bunga berbeda X dan Y, maka hasil F(N, XY) nya sama
Yakni, F(N, ab) = F(N, ba) = F(N, ac) = F(N, ca) = F(N, bc) = F(N, cb). Misalkan saja ini sama dengan F(N, XY)
Jika depannya ab, maka selanjutnya tidak boleh c (selanjutnya a atau b, ada dua kasus)
Dari dua kasus tersebut pandang digit kedua hingga akhir. Terdapat subproblem :

1. a b a _ _ _ ... Subprolem untuk kasus ini F(n-1, ba) = F(N-1, XY)
2. a b b _ _ _ ... Subprolem untuk kasus ini F(n-1, bb) = F(N-1, XX)

Diperoleh F(N, XY) = F(N-1, XY) + F(N-1, XX)

 

Misalkan F(N, aa) adalah banyaknya cara menyusun N pot bunga (sesuai aturan) dimana dua bunga di depannya adalah aa
Berdasarkan kesimetrian, apapun bunga X, maka hasil F(N, XX) sama
Yakni, F(N, aa) = F(N, bb) = F(N, cc). Misalkan saja ini sama dengan F(N, XX)
Jika depannya aa, maka selanjutnya boleh a, b, maupun c
Dari tiga kasus tersebut pandang digit kedua hingga akhir. Terdapat subproblem :

1. a a a _ _ _ ... Subprolem untuk kasus ini F(n-1, aa) = F(N-1, XX)
2. a a b _ _ _ ... Subprolem untuk kasus ini F(n-1, ab) = F(N-1, XY)
3. a a c _ _ _ ... Subprolem untuk kasus ini F(n-1, ac) = F(N-1, XY)

Diperoleh F(N, XX) = F(N-1, XX) + 2*F(N-1, XY)

 

Dengan basis
F(2, XX) = 1,
F(2, XY) = 1

 

	2	3	4	5	6
XX	1	3	7	17	41
XY	1	2	5	12	29

 

Dimana untuk mencari penyusunan pot dengan panjang 6,
= F(6, ab) + F(6, ba) + F(6, ac) + F(6, ca) + F(6, bc) + F(6, cb) + F(6, aa) + F(6, bb) + F(6, cc)
= 6*F(6, XY) + 3*F(6, XX)
= 6*29 + 3*41
= 297