Soluţia foloseşte metoda programării dinamice.
O stare se reprezintă prin camera în care ne aflăm şi momentul de timp. Fie $bst[i][j]$ numărul maxim de bomboane culese până în momentul $i$ când ne găsim în camera $j$. O observaţie evidentă este că $bst[i][j]$ se poate modifica doar în momentele în care apar cutiile. Prin urmare, vom considera momentele de timp $i$ când apar cutiile, momente ce sunt în număr de $M$. De cine depinde această stare? Ştim că $bst[i - 1][1 ... N]$ a fost deja calculat în mod optim. Să notăm cu $T$ diferenţa de timp dintre momentele la care apare cutia $i$ şi cutia $i - 1$. Din acest moment $i$ şi cameră $j$ ne putem deplasa maxim $T$ camere spre stânga sau spre dreapta. De unde deducem că:
O stare se reprezintă prin camera în care ne aflăm şi momentul de timp. Fie $bst[i][j]$ numărul maxim de bomboane culese până în momentul $i$ când ne găsim în camera $j$. O observaţie evidentă este că $bst[i][j]$ se poate modifica doar în momentele în care apar cutiile. Prin urmare, vom considera momentele de timp $i$ când apar cutiile, momente ce sunt în număr de $M$. De cine depinde această stare? Ştim că $bst[i - 1][1 ... N]$ a fost deja calculat în mod optim. Să notăm cu $T$ diferenţa de timp dintre momentele la care apare cutia $i$ şi cutia $i - 1$. În acest moment $i$ şi cameră $j$ putem ajunge din maxim $T$ camere spre stânga sau spre dreapta, întrucât fiecare deplasare între două camere costă o unitate de timp. De unde deducem că:
* $bst[i][j] = Min { bst[i - 1][j - T], bst[i - 1][j - T + 1], ..., bst[i - 1][j], ..., bst[i - 1][j + T - 1], bst[i - 1][j + T] }$.
Va urma...
Metoda directă şi, aparent eficientă, constă în folosirea unui arbore de intervale pentru aflarea acestui minim. Însă, intervalul se deplasează, dacă vom considera indicii $j$ în ordine $1$, $2$, ..., $N$, constant spre dreapta, fiind reprezentat de un şir de valori de lungime constantă în care noile elemente se introduc prin dreapta şi altele se elimină prin stânga. Vom folosi un deque şi vom proceda ca în problemele precedente, eliminând poziţiile care nu sunt candidate la soluţie.
p=. !deque-si-aplicatii?bcrc.png 40%!
Complexitatea finală: O(M * N).
h2(#concluzii). Concluzii
Filozofia din spatele structurii de deque devine utilă, de obicei, în momentele finale ale rezolvării unei probleme. Însă, ce pot spune cu certitudine este că această structură de date pe cât este de simplă pe atât este de eficientă.
