Această problemă reprezintă o extindere în două dimensiuni a problemei anterioare 'Vila 2':deque-si-aplicatii#problema-2, unde am studiat cazul unidimensional al determinării pe un vector a maximului / minimului pentru fiecare subsecvenţă de o lungime fixată.
Cerinţa constă în amplasarea unui dreptunghi $R x C$ astfel încât valoarea maximă din interiorul său să fie cât mai mică. Una din ideile simple constă în fixarea colţului din stânga sus în toate cele $(M - R + 1) x (N - C + 1)$ poziţii şi determinarea maximului din interiorul său cu o altă parcurgere a celor $R x C$ elemente. Dar, să fixăm o linie $i$. Atunci, pentru a fixa colţul din stânga sus mai iterăm cu un indice $j$ între coloanele $1$ şi $N - C + 1$. De aici devine clar că atunci când avansăm indicele coloanei în dreptunghiul curent apare o nouă coloană, $j + C$, şi dispare coloana $j$. Dacă pentru fiecare coloană $j$ de pe linia curentă $i$ reţinem un $Max{~i,j~}$ egal cu maximul dintre elementele $P{~i,j~}, P{~i+1,j~},.. P{~i+R-1,j~}$, atunci pe linia fixată $i$ vom avea un vector din $N$ elemente (numărul de coloane al matricei $P$) alcătuit din valorile $Max{~i,1~}, Max{~i,2~}, Max{~i,3~}, ..., Max{~i,j~}, ..., Max{~i,N-1~}, Max{~i,N~}$. Iar pe acest vector va trebui să determinăm pentru fiecare subsecvenţă de $C$ elemente, valoarea maximă. Dintre toate subsecvenţele o vom alege pe cea cu valoarea maximă cea mai mică. Iar acest rezultat va fi o soluţie pentru linia fixată. Cu valorile din $Max$ precalculate, pentru fiecare linie avem complexitatea $O(N)$, deci $O(M * N)$ pentru întreaga matrice. Însă, implementând direct, valorile din $Max$ se calculează în $O(M * N * R)$. Mai sus am definit $Max{~i,j~}$ ca fiind maximul dintre $P{~i,j~}, P{~i+1,j~}, ..., P{~i+R-1,j~}$. Rezultă că $Max{~i+1,j~}$ este maximul dintre $P{~i+1,j~}, P{~i+2,j~}, ..., P{~i+R-1,j~}, P{~i+R,j~}$, adică maximul dintre elementele lui $Max{~i,j~}$ din care scoatem $P{~i,j~}$ şi adăugăm $P{~i+R,j~}$. De aici deducem că pentru fiecare coloană fixată, valorile lui $Max$ de pe coloana respectivă se reduc la a determina pentru fiecare subsecvenţă de lungime $R$ (numărul de linii al dreptunghiului de amplasat) elementul maxim. Aceste rezultate se obţin în $O(M)$ pentru fiecare coloană, deci $O(N * M)$ în total.
Cerinţa constă în amplasarea unui dreptunghi $R x C$ astfel încât valoarea maximă din interiorul său să fie cât mai mică. Una din ideile simple constă în fixarea colţului din stânga sus în toate cele $(M - R + 1) x (N - C + 1)$ poziţii şi determinarea maximului din interiorul său cu o altă parcurgere a celor $R x C$ elemente. Putem, în schimb, să fixăm o linie $i$, iar pentru a fixa colţul din stânga sus mai iterăm cu un indice $j$ între coloanele $1$ şi $N - C + 1$. De aici devine clar că atunci când avansăm indicele coloanei, în dreptunghiul curent apare o nouă coloană, $j + C$, şi dispare coloana $j$. Dacă pentru fiecare coloană $j$ de pe linia curentă $i$ reţinem un $Max{~i,j~}$ egal cu maximul dintre elementele $P{~i,j~}, P{~i+1,j~}, ..., P{~i+R-1,j~}$, atunci pe linia fixată $i$ vom avea un vector din $N$ elemente (numărul de coloane al matricei $P$) alcătuit din valorile $Max{~i,1~}, Max{~i,2~}, Max{~i,3~}, ..., Max{~i,j~}, ..., Max{~i,N-1~}, Max{~i,N~}$. Iar pe acest vector va trebui să determinăm pentru fiecare subsecvenţă de $C$ elemente, valoarea maximă. Dintre toate subsecvenţele o vom alege pe cea cu valoarea maximă cea mai mică. Iar acest rezultat va fi o soluţie pentru linia fixată. Cu valorile din $Max$ precalculate, pentru fiecare linie avem complexitatea $O(N)$, deci $O(M * N)$ pentru întreaga matrice. Însă, implementând direct, valorile din $Max$ se calculează în $O(M * N * R)$. Mai sus am definit $Max{~i,j~}$ ca fiind maximul dintre $P{~i,j~}, P{~i+1,j~}, ..., P{~i+R-1,j~}$. Rezultă că $Max{~i+1,j~}$ este maximul dintre $P{~i+1,j~}, P{~i+2,j~}, ..., P{~i+R-1,j~}, P{~i+R,j~}$, adică maximul dintre elementele lui $Max{~i,j~}$ din care scoatem $P{~i,j~}$ şi adăugăm $P{~i+R,j~}$. De aici deducem că pentru fiecare coloană fixată, valorile lui $Max$ de pe coloana respectivă se reduc la a determina pentru fiecare subsecvenţă de lungime $R$ (numărul de linii al dreptunghiului de amplasat) elementul maxim. Aceste rezultate se obţin în $O(M)$ pentru fiecare coloană, deci $O(N * M)$ în total.
Rezultă complexitatea finală $O(M * N)$.
h2(#problema-5). 5. 'Trans':problema/trans (ONI 2004)
bq. Se dau $N$ blocuri de piatră, de culoare albă sau neagră aşezate în ordinea $1$, $2$,.., $N$. Blocurile de piatră trebuie să fie transportate în ordinea în care sunt, iar pentru aceasta va trebui închiriat un camion. Se mai dau $Q$ tipuri de camioane. Camionul de tipul $i (1 ≤ i ≤ Q)$ poate transporta maxim $K{~i~}$ blocuri de piatră la un moment dat şi pentru un transport se percepe taxa $T{~i~}$. Se impune condiţia ca toate blocurile de piatră plasate în camion la un transport sa aibă aceeaşi culoare. Aşadar, pentru a fi transportate toate blocurile, se va alege un camion de un anumit tip, iar camionul va efectua unul sau mai multe transporturi. Pentru a micşora suma totală plătită, există posibilitatea de a schimba culoarea oricărui bloc de piatră (din alb în negru sau din negru în alb); pentru fiecare bloc $i (1 ≤ i ≤ N)$ se cunoaşte suma $S{~i~}$ ce trebuie plătită pentru a-i schimba culoarea $C{~i~}$.
bq. Se dau $N$ blocuri de piatră, de culoare albă sau neagră aşezate în ordinea $1$, $2$, ..., $N$. Blocurile de piatră trebuie să fie transportate în ordinea în care sunt, iar pentru aceasta va trebui închiriat un camion. Se mai dau $Q$ tipuri de camioane. Camionul de tipul $i (1 ≤ i ≤ Q)$ poate transporta maxim $K{~i~}$ blocuri de piatră la un moment dat şi pentru un transport se percepe taxa $T{~i~}$. Se impune condiţia ca toate blocurile de piatră plasate în camion la un transport sa aibă aceeaşi culoare. Aşadar, pentru a fi transportate toate blocurile, se va alege un camion de un anumit tip, iar camionul va efectua unul sau mai multe transporturi. Pentru a micşora suma totală plătită, există posibilitatea de a schimba culoarea oricărui bloc de piatră (din alb în negru sau din negru în alb); pentru fiecare bloc $i (1 ≤ i ≤ N)$ se cunoaşte suma $S{~i~}$ ce trebuie plătită pentru a-i schimba culoarea $C{~i~}$.
Cerinţă: Pentru fiecare dintre cele $Q$ tipuri de camioane, determinaţi suma minimă plătită pentru a transporta toate cele $N$ blocuri.
Restricţii: $1 ≤ N ≤ 16 000$, $1 ≤ Q ≤ 100$, $1 ≤ K{~i~} ≤ N$.
Restricţii: $1 ≤ N ≤ 16.000$, $1 ≤ Q ≤ 100$, $1 ≤ K{~i~} ≤ N$.
h3. Soluţie:
Soluţia problemei se bazează pe găsirea unei formule de recurenţă ce respectă principiul optimalităţii al metodei programării dinamice.
Soluţia problemei se bazează pe găsirea unei formule de recurenţă ce respectă principiul optimalităţii specific metodei programării dinamice.
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 <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:
Î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_{j,c}\ :\ i - K \le j \le i - 1\ \} + sum_{i,c} + T; </tex>
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, după cum am arătat în problemele anterioare, 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> în şirul de indecşi de mai sus, el fiind egal cu <tex> Minim(bst_{i,0}, bst_{i,1}) - sum_{i,c} </tex>. 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>.
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} \le 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, după cum am arătat în problemele anterioare, 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} \le T_{i_{2},c} \le ... \le 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> în şirul de indecşi de mai sus, el fiind egal cu <tex> Minim(bst_{i,0}, bst_{i,1}) - sum_{i,c} </tex>. 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 <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, complexitatea soluţiei va fi <tex> O(N) </tex> pentru fiecare camion, deci <tex> O(Q * N) </tex> în total.
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 şi ştergeri pe la capete ($head$ şi $tail$), şir ce poate fi reprezentat printr-un deque. Cum fiecare index dintre <tex> 1, 2, \ldots, N </tex> va fi adăugat şi şters cel mult o singură dată din deque, complexitatea soluţiei va fi <tex> O(N) </tex> pentru fiecare camion, deci <tex> O(Q * N) </tex> în total.
În practică, programul este scurt, clar şi eficient:
Iată şi o sursă scurtă, clară şi eficientă pentru această problemă:
== code(cpp) |
#include <iostream>
