Soluţia problemei se bazează pe găsirea unei formule de recurenţă ce respectă principiul optimalităţii al metodei programării dinamice.
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$.
Pentru început, fixăm un camion dintre cele <tex> Q </tex>. Fie <tex> K </tex> numărul maxim de pietre pe care acesta le poate transporta şi <tex> T </tex> taxa percepută. Notăm <tex> sum_{i,c} </tex> costul pentru a schimba toate pietrele <tex> 1, 2, \ldots, i </tex> în culoarea <tex> c </tex> (<tex> c = 0 </tex> pentru alb şi <tex> c = 1 </tex> pentru negru). Rezultă că în <tex> sum_{i,c} </tex> se vor însuma toate valorile <tex> S_{j} </tex>, cu <tex> j \le i </tex> pentru care <tex> C_{j} = 1 - c </tex>.
Î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 <tex> bst_{i,c} </tex> costul minim pentru a transporta pietrele <tex> 1, 2, \ldots, i </tex>, iar ultimul transport conţine pietre de culoare <tex> c </tex>. Întrucât nu putem transporta mai mult de <tex> K </tex> pietre, <tex> bst_{i,c} </tex> depinde doar de poziţiile <tex> i - K, i - K + 1, \ldots, i - 1 </tex>. Cunoaştem că ultimul camion va transporta o secvenţă continuă de pietre începând de la o poziţie <tex> j + 1 </tex> până la poziţia <tex> i </tex>, unde <tex> i - K \le j \le i - 1 </tex>. Astfel, pentru fiecare <tex> j </tex> în intervalul precedent, costul va fi <tex> Min(bst_{j,0}, bst_{j,1}) </tex> (transportăm primele <tex> j </tex> pietre cât mai ieftin) adunat cu <tex> sum_{i,c} - sum_{j,c} </tex> (costul transformării pietrelor <tex> j + 1, \ldots, i </tex> în culoarea <tex> c </tex>) şi plus taxa <tex> T </tex>. 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>
* <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>
Dacă ne vom opri aici, complexitatea soluţiei va fi $O(Q * N^2^)$.
Dacă ne vom opri aici, complexitatea soluţiei va fi <tex> O(Q * N^{2}) </tex>.
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ţă:
Relaţia de recurenţă poate fi îmbunătăţită. Observăm că pentru poziţia <tex> i </tex>, <tex> sum_{i,c} </tex> este o valoare constantă, ca şi <tex> T </tex>. 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>
* <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>
Notez în continuare, pentru uşurinţă în scriere, $X[j][c] = Min(bst[j][0], bst[j][1]) - sum[j][c]$. Să fixăm doi indici $i{~1~}$ şi $i{~2~}$, astfel încât $i - K ≤ $i{~1~}$ < $i{~2~}$ ≤ i - 1$. Dacă $X[i{~1~}][c] > X[i{~2~}][c]$ 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~}][c] < X[i{~2~}][c]$, 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 ≤ i{~1~} < i{~2~} < .. < i{~n~} ≤ i - 1$ astfel încât $X[i{~1~}][c] < X[i{~2~}][c] < .. < X[i{~n~}][c]$. Mai departe, găsim $bst[i][c]$ ca fiind $X[i{~1~}][c] + sum[i][c] + T$. Urmează să îl introducem şi pe $X[i][c]$, el fiind egal cu $Min(bst[i][0], bst[i][1]) - sum[i][c]$, î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~}$][c] > X[i][c]$, $X[$i{~n-1~}$][c] > X[i][c]$, ... 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$...
Notez în continuare, pentru uşurinţă în scriere, <tex> T_{j,c} = Min(bst_{j,0}, bst_{j,1}) - sum_{j,c} </tex>. Să fixăm doi indici <tex> i_{1} </tex> şi <tex> i_{2} </tex>, astfel încât <tex> i - K \le i_{1} < i_{2} \le i - 1 </tex>. Dacă <tex> T_{i_{1},c} > T_{i_{2},c} </tex> atunci, întotdeauna poziţia <tex> i_{2} </tex> va fi preferată poziţiei <tex> i_{1} </tex>. Când cele două nu se vor mai afla ambele în intervalul <tex> [i - K, i - 1] </tex>, poziţia eliminată va fi poziţia <tex> i_{1} </tex>. Dacă <tex> T_{i_{1},c} < T_{i_{2},c} </tex>, 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 <tex> [i - K, i - 1] </tex> vom avea o serie de indecşi candidaţi la minim <tex> i - K \le i_{1} < i_{2} < \ldots < i_{n} \le i - 1 </tex> astfel încât <tex> T_{i_{1},c} < T_{i_{2},c} < .. < T_{i_{n},c} </tex>. Mai departe, găsim <tex> bst_{i,c} = T_{i_{1},c} + sum_{i,c} + T </tex>. Urmează să îl introducem şi pe <tex> T_{i,c} </tex>, el fiind egal cu <tex> Minim(bst_{i,0}, bst_{i,1}) - sum_{i,c} </tex>, în şirul de indecşi de mai sus. Acest lucru se va face în felul următor: se vor elimina din <tex> i_{n}, , i_{n-1}, \ldots </tex> atâta timp cât <tex> T_{i_{n},c} > T_{i,c} </tex>, <tex> T_{i_{n-1},c} > T_{i,c} \ldots </tex> adică atâta timp cât poziţia <tex> i </tex> este preferată lui <tex> i_{n}, i_{n-1}, \ldots </tex>. Fiind la poziţia <tex> i + 1 </tex>, intervalul se va transforma în <tex> [i - K + 1, i] </tex>, aşadar, vom mai elimina din primii indici <tex> i_{1}, i_{2}, \ldots </tex> atâta timp cât <tex> i_{1} < i - K + 1, i_{2} < i - K + 1, \ldots </tex>.
După cum am arătat şi la problema precedentă, acest şir de indecşi $i{~1~}$, $i{~2~}$, .., $i{~n~}$ are proprietatea că este un şir continuu de numere care admite inserări prin dreapta (tail) şi ştergeri prin stânga (head). Şir ce poate fi reprezentat printr-un deque. Cum fiecare index dintre $1$, $2$, .., $N$ va trece o singură dată prin deque şi va fi şters cel mult o dată, complexitatea soluţiei în acest caz va fi $O(Q * N)$.
După cum am arătat şi la problema precedentă, acest şir de indecşi <tex> i_{1}, i_{2}, \ldots, i_{n} </tex> are proprietatea că este un şir continuu de numere care admite inserări prin dreapta (tail) şi ştergeri prin stânga (head). Şir ce poate fi reprezentat printr-un deque. Cum fiecare index dintre <tex> 1, 2, \ldots, N </tex> va trece o singură dată prin deque şi va fi şters cel mult o dată, complexitatea soluţiei în acest caz va fi <tex> O(Q * N) </tex>.
În practică, programul este scurt, clar şi foarte eficient:
