Valorile initiale sunt:

* cmin[ 0 ][ 0 ][ 0 ] = cmin[ 0 ][ 0 ][ 1 ] = 0
* cmin[ 0 ][ i ][ 0 ] = cmin[ 0 ][ i ][ 1 ] = infinit, pentru i > 0

* $cmin[ 0 ][ 0 ][ 0 ] = cmin[ 0 ][ 0 ][ 1 ] = 0$
* $cmin[ 0 ][ i ][ 0 ] = cmin[ 0 ][ i ][ 1 ] = infinit$, pentru $i > 0$

Observand ca in relatiile de recurenta toate valorile cmin[i][a][b] depind doar de valori de tipul cmin[i-1][a{~1~}][b{~1~}] si cmin[i][a{~2~}][b{~2~}], putem retine doar ultimele 2 linii ale matricii cmin, pentru a nu ocupa prea multa memorie.

Observand ca in relatiile de recurenta toate valorile $cmin[i][a][b]$ depind doar de valori de tipul $cmin[i-1][a{~1~}][b{~1~}]$ si $cmin[i][a{~2~}][b{~2~}]$, putem retine doar ultimele $2$ linii ale matricii $cmin$, pentru a nu ocupa prea multa memorie.

Prima solutie pleaca de la implementarea directa a relatiilor de recurenta si are complexitatea O(N^2^*K), in conditiile in care putem calcula in O(1) sumele dupa p ce apar in relatiile de recurenta. Acest lucru se poate realiza usor, calculand in timp O(N) urmatoarii vectori:

Prima solutie pleaca de la implementarea directa a relatiilor de recurenta si are complexitatea $O(N^2^*K)$, in conditiile in care putem calcula in $O(1)$ sumele dupa $p$ ce apar in relatiile de recurenta. Acest lucru se poate realiza usor, calculand in timp $O(N)$ urmatoarii vectori:

* csum[i] = suma cantitatilor de combusitibil din benzinariile 1,..,i ; csum[i] = csum[i-1]+c[i]
* cright[i] = suma costurilor de a transporta cantitatile necesare de combustibil de la benzinaria N la fiecare din benzinariile i, i+1,..,N ; cright[i] = cright[i+1] + c[i] * (d[N] - d[i])
* cleft[i] = suma costurilor de a transporta cantitatea dorita de combustibil de la benzinaria N la benzinariile i, i+1,..,N ; cleft[i] = cleft[i-1] + c[i] * (d[i] - d[ 1 ])

* $csum[i] =$ suma cantitatilor de combusitibil din benzinariile $[1..i]$ ; $csum[i] = csum[i-1]+c[i]$
* $cright[i] =$ suma costurilor de a transporta cantitatile necesare de combustibil de la benzinaria $N$ la fiecare din benzinariile $[i..N]$ ; $cright[i] = cright[i+1] + c[i] * (d[N] - d[i])$
* $cleft[i] =$ suma costurilor de a transporta cantitatea dorita de combustibil de la benzinaria $N$ la benzinariile $[i..N]$ ; $cleft[i] = cleft[i-1] + c[i] * (d[i] - d[ 1 ])$

Cu acesti vectori, !autumn-warmup-2007/solutii/runda-2?rompetrol-p3.jpg! se scrie ca fiind egala cu cright[j{~1~}+1] - cright[j+1] - (csum[j] - csum[j{~1~}]) * (d[N] - d[j]). In mod similar, !autumn-warmup-2007/solutii/runda-2?rompetrol-p4.jpg! se scrie ca fiind egala cu cleft[j] - cleft[j{~1~}] - (csum[j] - csum[j{~1~}])*(d[j{~1~}] - d[ 1 ]).

Cu acesti vectori, !autumn-warmup-2007/solutii/runda-2?rompetrol-p3.jpg! se scrie ca fiind egala cu $cright[j{~1~}+1] - cright[j+1] - (csum[j] - csum[j{~1~}]) * (d[N] - d[j])$. In mod similar, !autumn-warmup-2007/solutii/runda-2?rompetrol-p4.jpg! se scrie ca fiind egala cu $cleft[j] - cleft[j{~1~}] - (csum[j] - csum[j{~1~}])*(d[j{~1~}] - d[ 1 ])$.

Solutia optima are, insa, complexitatea O(N*K) si se bazeaza pe urmatoarele concepte: pentru fiecare  i de la 1 la K si fiecare pozitie j de la 1 la N vom defini doua functii f{~i,j~} si g{~i,j~}, pe care le vom folosi in calculul valorilor cmin[ i ][ j ][ 0 ] si cmin[ i ][ j ][ 1 ].

Solutia optima are, insa, complexitatea $O(N*K)$ si se bazeaza pe urmatoarele concepte: pentru fiecare $i$ de la $1$ la $K$ si fiecare pozitie $j$ de la $1$ la $N$ vom defini doua functii $f{~i,j~}$ si $g{~i,j~}$, pe care le vom folosi in calculul valorilor $cmin[ i ][ j ][ 0 ]$ si $cmin[ i ][ j ][ 1 ]$.

h3. {*Calculul valorilor cmin[ i ][ j ][ 0 ]*}

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.