== include(page="template/taskheader" task_id="costsq") ==

Se da o secventa cu $N$ elemente: $w(1), ..., w(N)$. Dorim sa impartim aceasta secventa in $K$ subsecvente disjuncte (o subsecventa consta din elemente consecutive ale secventei date), in asa fel incat fiecare element al secventei apartine exact unei singure subsecvente. Notam prin $S[i:j]$ subsecventa care incepe la pozitia $i$ si se termina la pozitia $j$. Costul lui $S[i:j]$ este $(w(i)+w(i+1)+...+w(j))^2^$. Costul unei impartiri este egal cu suma costurilor celor $K$ subsecvente. Determinati o impartire a secventei date in $K$ subsecvente disjuncte, astfel incat costul impartirii sa fie minim.

Se da o secventa cu $N$ elemente: $w(1), ..., w(N)$. Dorim sa impartim aceasta secventa in $K$ subsecvente disjuncte (o subsecventa consta din elemente consecutive ale secventei date), in asa fel incat fiecare element al secventei apartine exact unei singure subsecvente. Notam prin $S[i:j]$ subsecventa care incepe la pozitia $i$ si se termina la pozitia $j$. Costul lui $S[i:j]$ este $(w(i)+w(i+1)+...+w(j))^2^$. Costul unei impartiri in $K$ subsecvente este egal cu suma costurilor celor $K$ subsecvente. Determinati o impartire a secventei date in $K$ subsecvente disjuncte, astfel incat costul impartirii sa fie minim.

In plus, se dau si o serie de constrangeri suplimentare. Daca din impartire face parte subsecventa $S[i:j]$, atunci $i$ trebuie sa respecte urmatoarele constrangeri: $l(j) ≤ i ≤ u(j)$ (mai exact, daca alegem ca una din subsecvente sa se termine la pozitia $j$, atunci pozitia de inceput a subsecventei trebuie sa fie intre $l(j)$ si $u(j)$). Valorile $l(j)$ si $u(j)$ au urmatoarele proprietati: