h3. (problema usoara, clasele 11-12)

Problema se rezolva prin metoda programarii dinamice. Vom calcula $Nr[i][j]$ numarul de p-subsiruri care au ultimiii doi termeni $a{~i~}$ si $a{~j~} (i < j)$.

Problema se rezolva prin metoda programarii dinamice. Conditia din enunt se poate enunta astfel: elementul $a{~i~}$ dintr-un p-sir trebuie sa fie inclus strict in intervalul determinat de $a{~i-1~}$ si $a{~i-2~}$. Vom calcula $Nr[i][j]$ numarul de p-subsiruri care au ultimiii doi termeni $P{~i~}$ si $P{~j~} (i < j)$.
Vom presupune ca $P{~i~} < P{~j~}$, cazul $P{~i~} > P{~j~}$ putand fi tratat asemanator. $Nr[i][j]$ se va calcula ca suma de $Nr[k][i]$ cu proprietatea $P{~i~} < P{~j~} < P{~k~}$. O implementare directa a acestei rezolvari are complexitatea $O(N^3^)$ si ar fi obtinut $30$ de puncte. Daca sortam vectorul $P$ dat la intrare, valorile $k < i$ care respecta conditia $P{~j~} < P{~k~}$ vor forma un interval continuu ca indici.
 

h2. 'Eval':problema/eval