Pentru $S[] = {5, 9, 4, 7, 4, 1}$ şi $D = 3$ obţinem următoarele stări ale unui deque:

* <tex> \langle \widehat{5\ [1]} \rangle; </tex>
* <tex> \langle 5\ [1] \rangle \Leftarrow 9\ [2] </tex> de unde se obţine <tex> \langle \widehat{9\ [2]} \rangle; </tex>
* <tex> \langle 9\ [2] \rangle \Leftarrow 4\ [3] </tex> de unde se obţine <tex> \langle \widehat{9\ [2]},\ 4\ [3] \rangle; </tex>
* <tex> \langle 9\ [2],\ 4\ [3] \rangle \Leftarrow 7\ [4] </tex> de unde se obţine <tex> \langle \widehat{9\ [2]},\ 7\ [4] \rangle; </tex>
* <tex> 9\ [2] \Leftarrow \langle 7\ [4] \rangle \Leftarrow 4\ [5] </tex> de unde se obţine <tex> \langle \widehat{7\ [4]},\ 4\ [5] \rangle; </tex>
* <tex> \langle 7\ [4],\ 4\ [5] \rangle \Leftarrow 1\ [6] </tex> de unde se obţine <tex> \langle \widehat{7\ [4]},\ 4\ [5],\ 1\ [6] \rangle; </tex>

p=. !deque-si-aplicatii?vila22.png 60%!

Cum fiecare indice din $1$, $2$, .., $N$ trece cel mult o dată prin deque, complexitatea finală este $O(N)$ amortizat.

Pentru început, fixăm un camion dintre cele $Q$. Fie $K$ numărul maxim de pietre pe care acesta le poate transporta şi $T$ taxa percepută. Notăm $sum[i][c]$ costul pentru a schimba toate pietrele $1$, $2$, .., $i$ în culoarea $c$ ({$c = 0$} pentru alb şi $c = 1$ pentru negru). În $sum[i][c]$ se vor aduna toate valorile $S[j]$, cu $j ≤ i$ pentru care $C[j] = 1 - c$.

În continuare, considerăm $bst[i][c]$ costul minim pentru a transporta pietrele $1$, $2$, .., $i$, iar ultimul transport conţine pietre de culoare $c$. Întrucât nu putem transporta mai mult de $K$ pietre, $bst[i][c]$ depinde doar de poziţiile $i - K$, $i - K + 1$, ..., $i - 1$. Cunoaştem că ultimul camion va transporta o secvenţă continuă de pietre începând de la o poziţie $j + 1$ până la poziţia $i$, unde $i - K ≤ j ≤ i - 1$. Astfel, pentru fiecare $j$ în intervalul precedent, costul va fi $Minim(bst[j][0], bst[j][1])$ (transportăm primele j pietre cât mai ieftin) adunat cu $sum[i][c] - sum[j][c]$ (costul transformării pietrelor $j + 1$, .., $i$ în culoarea $c$) şi plus taxa $T$. Rezultă recurenţa:

În continuare, considerăm $bst[i][c]$ costul minim pentru a transporta pietrele $1$, $2$, .., $i$, iar ultimul transport conţine pietre de culoare $c$. Întrucât nu putem transporta mai mult de $K$ pietre, $bst[i][c]$ depinde doar de poziţiile $i - K$, $i - K + 1$, ..., $i - 1$. Cunoaştem că ultimul camion va transporta o secvenţă continuă de pietre începând de la o poziţie $j + 1$ până la poziţia $i$, unde $i - K ≤ j ≤ i - 1$. Astfel, pentru fiecare $j$ în intervalul precedent, costul va fi $Min(bst[j][0], bst[j][1])$ (transportăm primele j pietre cât mai ieftin) adunat cu $sum[i][c] - sum[j][c]$ (costul transformării pietrelor $j + 1$, .., $i$ în culoarea $c$) şi plus taxa $T$. Rezultă recurenţa:

* <tex> bst[i][c] = Min\ \{\ Minim(bst[j][0],\ bst[j][1]) + sum[i][c] - sum[j][c] + T\ |\ i - K \le j \le i - 1\ \}; </tex>

* $bst[i][c] = Min{ Min(bst[j][0], bst[j][1]) + sum[i][c] - sum[j][c] } + T$, unde $i - K ≤ j ≤ i - 1$.

Dacă ne vom opri aici, complexitatea soluţiei va fi $O(Q * N^2^)$.
Relaţia de recurenţă poate fi îmbunătăţită. Observăm că pentru poziţia $i$, $sum[i][c]$ este o valoare constantă, ca şi $T$. Astfel, deducem următoarea relaţie de recurenţă:

* <tex> bst[i][c] = Min\ \{\ Minim(bst[j][0],\ bst[j][1]) - sum[j][c]\ |\ i - K \le j \le i - 1\ \} + sum[i][c] + T; </tex>

* $bst[i][c] = Min{ Min(bst[j][0], bst[j][1]) - sum[j][c] } + sum[i][c] + T$, unde $i - K ≤ j ≤ i - 1$.

Notez în continuare, pentru uşurinţă în scriere, $X[j][&#99;] = Min(bst[j][&#48;], bst[j][&#49;]) - sum[j][&#99;]$. Să fixăm doi indici $i{~1~}$ şi $i{~2~}$, astfel încât $i - K &le; $i{~1~}$ < $i{~2~}$ &le; i - 1$. Dacă $X[i{~1~}][&#99;] > X[i{~2~}][&#99;]$ atunci, întotdeauna poziţia $i{~2~}$ va fi preferată poziţiei $i{~1~}$. Când cele două nu se vor mai afla în intervalul $[i - K, i - 1]$, poziţia eliminată va fi poziţia $i{~1~}$. Dacă $X[i{~1~}][&#99;] < X[i{~2~}][&#99;]$, atunci nu putem decide care poziţie este mai bună în viitor, aşa că le vom păstra pe ambele. Rezultă mai departe că în intervalul $[i - K, i - 1]$ vom avea o serie de indecşi candidaţi la minim $i - K &le; i{~1~} < i{~2~} < .. < i{~n~} &le; i - 1$ astfel încât $X[i{~1~}][&#99;] < X[i{~2~}][&#99;] <  .. < X[i{~n~}][&#99;]$. Mai departe, găsim $bst[i][&#99;]$ ca fiind $X[i{~1~}][&#99;] + sum[i][&#99;] + T$. Urmează să îl introducem şi pe $X[i][&#99;]$, el fiind egal cu $Min(bst[i][&#48;], bst[i][&#49;]) - sum[i][&#99;]$, în şirul de indecşi de mai sus. Acest lucru se va face în felul următor: se vor elimina din $i{~n~}$, $i{~n-1~}$, ... atâta timp cât $X[$i{~n~}$][&#99;] > X[i][&#99;]$, $X[$i{~n-1~}$][&#99;] > X[i][&#99;]$, ... adică atâta timp cât poziţia $i$ este preferată lui $i{~n~}$, $i{~n-1~}$... Fiind la poziţia $i + 1$, intervalul se va transforma în $[i - K + 1, i]$, aşadar, vom mai elimina din primii indici $i{~1~}$, $i{~2~}$,... atâta timp cât $i{~1~} < i - K + 1$, $i{~2~} < i - K + 1$...

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 când apar cutiile, momente ce sunt în număr de $M$, $bst[i][j]$ însemnând numărul maxim de bomboane culese ştiind că ne aflăm în camera $j$ unde am cules cutia $i$. 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ă:

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 când apar cutiile, momente ce sunt în număr de $M$, $bst[i][j]$ însemnând numărul maxim de bomboane culese ştiind că ne aflăm în camera $j$ unde am cules cutia $i$. 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ă:

* <tex> 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]\ \}; </tex>

* $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] }$.

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$, $3$, ... 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 de lungime $2 * T$ şi vom proceda ca în problemele precedente, eliminând poziţiile care nu sunt candidate la soluţie. Mai jos este o reprezentare grafică a acestei explicaţii.