Problema!

[•artuditu]

se cere de la tastatura un numar natural n care reprezinta numarul de artificii, urmate de citirea a n perechi de valori reale pozitive h si d,
reprezentand inaltimea la care s-au ridicat si durata de ardere. Sa se calculeze:
             a)inaltimea maxima si cate artificii au ajuns la aceasta.
             b)sa determin si sa afisez lungimea celei mai lungi secvente de artificii cu inaltimi crescatoare si durata medie de ardere a acestora. daca sunt mai multe secvente de aceeasi marime, se va afisa cea cu durata medie de ardere mai mare.
             !!!a-ul l-am rezolvat, dar am probleme la rezolvarea punctului b!!!

[•harababurel]

Punctul b) coincide cu problema determinarii secventei crescatoare de lungime maxima, care se rezolva prin metoda programarii dinamice:

Iti propui sa construiesti un sir dp() cu semnificatia dp(i) = lungimea maxima a unei secvente care incepe pe pozitia i, si este crescatoare.
Pe pozitia n exista o singura secventa (de lungime 1), deci dp(n) = 1 (asta e subproblema elementara).
Pentru orice alt indice i, care ia valori de la n-1 la 1, construiesti dinamica pe baza recurentei:
1) dp(i) = 1, daca v(i) > v(i+1)
2) dp(i) = 1 + dp(i+1), daca v(i) <= v(i+1)

Recurenta se interpreteaza asa:
1) daca valoarea curenta o depaseste pe cea din dreapta, inseamna ca nu pot construi o secventa cu ambele (nu ar fi crescatoare); construiesti deci secventa formata doar din elementul curent.
2) daca valoarea curenta nu o depaseste pe cea din dreapta, inseamna ca poti alatura elementul curent secventei optime care incepe cu elementul urmator (adica dp(i+1)) si obtii o secventa mai mare cu un element decat cea care incepe vecinul din dreapta.

La final cauti maximul din dp(), gasesti capetele secventei respective, calculezi media.