Folosind observatia ca fiecare functie este minima pe cel mult un interval, putem folosi un arbore de intervale pentru a stoca in el semidrepte. Aceasta este o utilizare oarecum neobisnuita a unui arbore de intervale, dar vom vedea ca este foarte utila in cazul acestei probleme. Pseudocodul solutiei este urmatorul:
* $; calculeaza vectorii SP si DP$

* $SP[0]=0$
* $DP[0]=0$

* $SP[ 0 ] = 0$
* $DP[ 0 ] = 0$

* $pentru i de la 1 la N$

** $SP[i]=SP[i-1]+S[i]$
** $DP[i]=DP[i-1]+D[i]$

** $SP[i] = SP[i-1] + S[i]$
** $DP[i] = DP[i-1] + D[i]$

* $; calculeaza vectorul cmin$

* $cmin[0]=0$

* $cmin[ 0 ] = 0$

* $pentru i de la 1 la N$

** $finit[i]=cmin[i-1]+F[i]$
** $P[i]=C[i]-SP[i-1]$
** $[li,ri]=find_interval(i) ; gaseste intervalul [li,ri] pe care functia fi este minima$

** $finit[i] = cmin[i-1] + F[i]$
** $P[i] = C[i] - SP[i-1]$
** $[li,ri] = find_interval(i) ; gaseste intervalul [li,ri] pe care functia fi este minima$

** $daca intervalul [li, ri] nu este vid$

*** $update(li,ri,i,radacina_arborelui_de_intervale)$
** $cmin[i]=get_min(i) ; determina valoarea minima in punctul i dintre toate functiile existente$
* $suma=0$

*** $update(li, ri, i, radacina_arborelui_de_intervale)$
** $cmin[i] = get_min(i) ; determina valoarea minima in punctul i dintre toate functiile existente$
* $suma = 0$

* $pentru i de la 1 la N$

** $suma=suma+SP[i-1]*D[i]$
* $afisaza cmin[N]+suma$

** $suma = suma + SP[i-1] * D[i]$
* $afisaza cmin[N] + suma$

Cele $3$ functii a caror implementare mai trebuie descrisa in detaliu sunt: $find_interval$, $update$ si $get_min$.

Pseudocodul pentru calculul capatului stanga al intervalului in care functia fi este minima este urmatorul:

* $*find_interval(i)*$

* $left=i$
* $right=N$
* $li=N+1$

Fiecare nod din arbore are o referinta catre tatal sau $(tata[nod])$. Radacina arborelui are o referinta catre o valoare nedefinita $(NEDEFINIT)$. Pseudocodul functiei $get_min$ este urmatorul:

* $get_min(i)$

* $*get_min(i)*$

* $nod = nodul din arbore corespunzator intervalului [i,i]$
* $val_min=infinit$
* $cat timp nod <> NEDEFINIT$