costsq

Costsq

== 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:

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:

* $1 ≤ l(j) ≤ u(j) ≤ j$
* $l(j) ≤ l(j+1)$ (pentru $1 ≤ j ≤ N-1$)

h2. Restricţii
* $1 ≤ N ≤ 100.000$

* $1 ≤ K ≤ 100$

* $1 ≤ K ≤ min{100,N}$

* $1 ≤ w(i) ≤ 1.000$
h2. Exemplu

5 4 8
4 4 9
9 7 10

|xxx

|1642

|
== include(page="template/taskfooter" task_id="costsq") ==