Pagini recente » Diferente pentru fmi-no-stress-4/solutii intre reviziile 43 si 42 | Diferente pentru fmi-no-stress-4/solutii intre reviziile 40 si 39 | Diferente pentru utilizator/alex_tz307 intre reviziile 135 si 118 | Diferente pentru utilizator/alex_tz307 intre reviziile 119 si 120 | Diferente pentru fmi-no-stress-4/solutii intre reviziile 24 si 23
Nu exista diferente intre titluri.
Diferente intre continut:
Problema ne cere sa aflam lungimea maxima $K$ a unui subsir de plicuri, astfel incat primul plic sa incapa in al doilea, al doilea in al treilea, ..., al $K-1$-lea in al $K$-lea. Intuitiv, aceasta cerinta ne duce cu gandul la un algoritm de tipul subsir crescator maximal. Pentru a aplica insa acest algoritm in cazul de fata, trebuie sa avem plicurile intr-o ordine convenabila. Vom sorta plicurile crescator dupa dimensiunea L a acestora, iar in caz de egalitate, descrescator dupa dimensiunea W. Astfel, pentru oricare doua plicuri $i$ si $j$, cu $i < j$, vom avea doua cazuri:
* $L[i] < L[j]$, deci este suficient sa comparam dimensiunea W ca sa ne dam seama daca plicul $i$ poate fi introdus in plicul $j$.
* $L[i] = L[j]$, deci $W[i] > W[j]$, datorita conditiei de sortare in caz de egalitate. Deci si in acest caz, este suficient sa comparam doar dimensiunea W a plicurilor pentru ne da seama ca plicurile nu pot fi introduse unul in celalalt.
* $L[i] = L[j]$, deci $W[i] > W[j]$, datorita conditiei de sortare in caz de egalitate. Deci si in acest caz, este suficient sa comparam doar dimensiunea W a plicurilor pentru a sti daca pot fi introduse unul in celalalt.
Asadar, in continuare putem aplica algoritmul de determinare a subsirului crescator maximal pe vectorul dimensiunii W a plicurilor, afisand lungimea determinata. Acest algoritm este explicat in detaliu la acest link: 'Scmax':problema/scmax.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.