h2. 'Rompetrol':problema/rompetrol

Vom calcula costurile cmin[ i ][ j ][ 0 ] si cmin[ i ][ j ][ 1 ], avand

Vom calcula costurile @cmin[ i ][ j ][ 0 ]@ si @cmin[ i ][ j ][ 1 ]@, avand semnificatiile:

semnificatiile:
 
* cmin[ i ][ j ][ 0 ] = costul minim pentru a amplasa in total i depozite in benzinariile 1,2,..,j, iar al i-lea depozit se afla localizat chiar in benzinaria j
* cmin[ i ][ j ][ 1 ] = costul minim pentru a amplasa in total i depozite in benzinariile 1,2,..,j, iar al i-lea depozit nu este neaparat amplasat in benzinaria j

* @cmin[ i ][ j ][ 0 ]@ = costul minim pentru a amplasa in total @i@ depozite in benzinariile @[1..j]@, iar al @i@-lea depozit se afla localizat chiar in benzinaria @j@
* @cmin[ i ][ j ][ 1 ]@ = costul minim pentru a amplasa in total @i@ depozite in benzinariile @[1..j@, iar al @i@-lea depozit nu este neaparat amplasat in benzinaria @j@

Relatiile de recurenta sunt urmatoarele:

Pentru fiecare pozitie j, vom defini functia f{~i,j~}:[d[j],d[N]] -> int. O valoare a acestei functii intr-un punct d[p], corespunzator benzinariei p, f{~i,j~}(d[p]), reprezinta costul minim pentru a amplasa i depozite in benzinariile 1,2,..,p, in conditiile in care al i-lea depozit este in benzinaria p, iar benzinariile j, j+1, .., p sunt alimentate cu combustibil de la depozitul din benzinaria p. Cu aceste definitii, valoarea lui cmin[ i ][ j ][ 0 ] este minimul dintre valorile functiilor f{~i,j{~1~}~}, in punctul d[j], cu 0<=j{~1~}<j, la care se adauga valoarea a[j]. Problema importanta este cum aflam minimul dintre aceste functii, fara a calcula valoarea fiecarei functii in punctul d[j] (care ar conduce la o complexitate O(N^2^*K)).

Formula unei functii f{~i,j~}(d[p]) este: cmin[ i-1 ][ j-1 ][ 1 ] + !autumn-warmup-2007/solutii/runda-2?rompetrol-p5.jpg! . Diferenta dintre 2 valori consecutive ale functiei, df{~i,j~}(d[p+1]) = f{~i,j~}(d[p+1]) � f{~i,j~}(d[p]), este egala cu (c[j]+c[j+1] + .. + c[p]) * (d[p+1] - d[p]). Asadar, de la un pas la altul, functiile f{~i,j~} care au un j mai mic cresc mai mult decat cele care corespund unei pozitii j mai mari (altfel spus, functiile care au �aparut� mai recent cresc mai incet decat functiile care au �aparut� de mai mult timp) : df{~i,j~}(d[p+1]) < df{~i,j{~1~}~}(d[p+1]), daca j{~1~} < j. De aici tragem urmatoarele concluzii:

Formula unei functii f{~i,j~}(d[p]) este: cmin[ i-1 ][ j-1 ][ 1 ] + !autumn-warmup-2007/solutii/runda-2?rompetrol-p5.jpg! . Diferenta dintre 2 valori consecutive ale functiei, df{~i,j~}(d[p+1]) = f{~i,j~}(d[p+1]) � f{~i,j~}(d[p]), este egala cu (c[j]+c[j+1] + .. + c[p]) * (d[p+1] - d[p]). Asadar, de la un pas la altul, functiile f{~i,j~} care au un j mai mic cresc mai mult decat cele care corespund unei pozitii j mai mari (altfel spus, functiile care au �aparut� mai recent cresc mai incet decat functiile care au �aparut� de mai mult timp) : df{~i,j~}(d[p+1]) < df{~i,j{~1~}~}(d[p+1]), daca j{~1~} < j. De aici tragem urmatoarele concluzii:

* daca valoarea unei functii fi,j(d[p+1]) este mai mare decat valoarea unei functii f{~i,j{~1~}~}(d[p+1]), cu j{~1~}>j, atunci functia f{~i,j~} nu va mai avea niciodata valoarea minima dintre toate functiile la nici unul din pasii ulteriori.
* daca valoarea unei functii f{~i,j~}(d[p+1]) este mai mica decat valoarea unei functii f{~i,j{~1~}~}(d[p+1]), cu j{~1~}>j, atunci functia f{~i,j~} va fi 'depasita' de functia f{~i,j{~1~}~} intr-un punct x{~j,j{~1~}~} ; maximul dupa j dinte valorile x{~j,j{~1~}~} reprezinta punctul minim posibil la care functia f{~i,j{~1~}~} va avea valoarea minima dintre toate functiile dinaintea ei.