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 ]*}

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)).

usor ca acest lucru este adevarat, pentru ca pantele dreptelor asociate cresc cu aceeasi valoare in fiecare punct in care se afla localizata o benzinarie. Prin urmare, punctul x in care functia f{~i,j{~1~}~} depaseste functia f{~i,j~} este x=d[j{~1~}] + dC/dP.

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

h3. Calculul valorilor cmin[ i ][ j ][ 1 ]

Calculul valorilor $cmin[ i ][ j ][ 1 ]$ se realizeaza similar cu calculul valorilor $cmin[ i ][ j ][ 0 ]$. Se vor defini niste functii $g{~i,j~}:[csum[j], csum[N]]$, ale caror valori $g{~i,j~}(csum[p])$ vor reprezenta costul minim pentru a amplasa $i$ depozite in benzinariile $[1..p]$, in conditiile in care al $i$-lea depozit este amplasat in benzinaria $j$. Aceste functii sunt definite pe sumele partiale ale cantitatilor de combustibil pentru a putea folosi un rationament asemanator celui prezentat mai sus si a privi fiecare functie ca o dreapta in intervalul dintre sumele partiale corespunzatoare a doua benzinarii consecutive. Panta unei functii $g{~i,j~}$ intr-un punct $csum[j{~1~}] (j{~1~}>j)$ va fi, conform acestor definitii, $d[j{~1~}]-d[j]$.

h3. {*Probleme asemanatoare*}

h3. Probleme asemanatoare

* 'leaves [.campion 2005]':http://campion.edu.ro/problems/3/260/leaves_ro.htm
* 'batch [IOI 2002]':http://olympiads.win.tue.nl/ioi/ioi2002/contest/day2/batch/batch.pdf

h3. {*Articole utile*}

h3. Articole utile

* 'http://citeseer.ist.psu.edu/87954.html':http://citeseer.ist.psu.edu/87954.html
* 'http://www.cse.ust.hk/faculty/golin/pubs/KMedian_SWAT04.pdf':http://www.cse.ust.hk/faculty/golin/pubs/KMedian_SWAT04.pdf