|
Titlul: Problema! Scris de: Tohatan Cristi din Decembrie 12, 2013, 20:52:05 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!!! Titlul: Răspuns: Problema! Scris de: Puscas Sergiu din Decembrie 20, 2013, 20:19:20 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. |