h3(#problema-3). Problema 3: 'Trans':problema/trans (ONI 2004)
bq. Se dau $N$ blocuri de piatră, de culoare albă sau neagră. Ele sunt asezate in ordinea $1$, $2$,.., $N$. Blocurile de piatră trebuie să fie transportate în ordinea în care sunt depozitate, iar pentru aceasta va trebui inchiriat 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 pe şantier, compania de construcţii 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ă, compania de construcţii are 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.
Cerinţă: Pentru fiecare dintre cele $Q$ tipuri de camioane deţinute de compania de transport, determinaţi suma minimă pe care o va plăti compania de construcţii pentru a transporta toate cele $N$ blocuri pe şantier.
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.
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$.
h3. Soluţie:
* $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][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 î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]$. Când trebuie să avansăm la poziţia $i + 1$ vom elimina din $i{~1~}$, $i{~2~}$, .. cât timp aceştia vor fi mai mici sau egali decât $i - K$. De asemenea, 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~}$...
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$...
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). Care poate fi, deci, 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 $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)$.
În practică, programul poate arăta în felul următor:
