h3(#problema-3). Problema 3: 'Trans':problema/trans (ONI 2004)

(gen bun de problema)
...

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.
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.
 
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 $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:
 
* $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ţă:
 
* $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 î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;]$. Când vom avansa la poziţia $i + 1$ vom elimina din $i{~1~}$, $i{~2~}$, .. cât timp aceştia vor fi mai mici strict decât $i - K$. De asemenea, găsim $bst[i + 1][&#99;]$ ca fiind $X[i{~1~}][&#99;] + sum[i + 1][&#99;] + T$. Urmează să îl introducem şi pe $X[i + 1][&#99;]$, el fiind egal cu $Min(bst[i + 1][&#48;], bst[i + 1][&#49;]) - sum[i + 1][&#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~}$] > X[i + 1]$, $X[$i{~n-1~}$] > X[i + 1]$, ... adică atâta timp cât poziţia $i + 1$ este preferată.
 
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)$.
 
În practică, programul poate arăta în felul următor:
 
== code(cpp) |
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
 
const char iname[] = "trans.in";
const char oname[] = "trans.out";
 
#define MAXN  16005
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define FOR(i, a, b)  for (int i = (a); i <= (b); ++ i)
 
int C[MAXN], S[MAXN], bst[MAXN][2], sum[MAXN][2], N;
 
void insert(deque < pair <int, int> >& deq, const pair <int, int>& p) {
    while (!deq.empty() && deq.back().second > p.second)
        deq.pop_back();
    deq.push_back(p);
}
 
int query(deque < pair <int, int> >& deq, const int idx) {
    while (deq.front().first < idx)
        deq.pop_front();
    return deq.front().second;
}
 
int work(const int K, const int T) {
    deque < pair <int, int> > deq[2];       // pair (idx, value)
    FOR (c, 0, 1)
        insert(deq[c], pair <int, int>(0, 0));
    FOR (i, 1, N) {   // obiectul i
        FOR (c, 0, 1) // culoare
            bst[i][c] = query(deq[c], i - K) + sum[i][c] + T;
        FOR (c, 0, 1)
            insert(deq[c], pair <int, int>(i, Min(bst[i][0], bst[i][1]) - sum[i][c]));
    }
    return Min(bst[N][0], bst[N][1]);
}
 
int main(void)
{
    ifstream in(iname);  ofstream out(oname);
    in >> N;
    FOR (i, 1, N) {
        in >> C[i] >> S[i];
        FOR (c, 0, 1)
            sum[i][c] += sum[i - 1][c];
        sum[i][1 - C[i]] += S[i];
    }
    int cnt;
    in >> cnt;
    FOR (i, 1, cnt) {
        int K, T;
        in >> K >> T;
        out << work(K, T) << "\n";
    }
    in.close(), out.close();
    return 0;
}
==

h3(#problema-4). Problema 4: 'Otilia':problema/otilia  (.campion)