Pagini recente » Clasament hc2 | Diferente pentru blog/cum-fac-altii intre reviziile 4 si 3 | Diferente pentru schimbare-borland/argumentatie intre reviziile 27 si 21 | Diferente pentru utilizator/nicolaetitus12 intre reviziile 15 si 10 | Diferente pentru monthly-2014/runda-3/solutii intre reviziile 9 si 10
Nu exista diferente intre titluri.
Diferente intre continut:
h1. 'Concert2':problema/concert2
Problema se rezolva cu ajutorul programarii dinamice:
Se constrieste dinamica dp[i][j][p]= lungimea maxima a unui subsir care respecta proprietatile din enunt si se termina pe pozitia i iar ultima secventa crescatoare are lungimea j pentru p = 0 si lungimea maxima a unui subsir care respecta proprietatile din enunt si se termina pe pozitia i iar ultima secventa descrescatoare are lungimea j pentru p = 1.O recurenta in O(n) nu se incadreaza in timp, de aceea va trebui sa construim 2*K arbori de intervale pentru a putea calcula in timp logaritmic maximul pe un interval.Pentru asta este necesar sa normalizam datele de intrare.
Se construieste dinamica dp[i][j][p]= lungimea maxima a unui subsir care respecta proprietatile din enunt si se termina pe pozitia i iar ultima secventa crescatoare are lungimea j pentru p = 0 si lungimea maxima a unui subsir care respecta proprietatile din enunt si se termina pe pozitia i iar ultima secventa descrescatoare are lungimea j pentru p = 1.O recurenta in O(n) nu se incadreaza in timp, de aceea va trebui sa construim 2*K arbori de intervale pentru a putea calcula in timp logaritmic maximul pe un interval.Pentru asta este necesar sa normalizam datele de intrare.
Solutia se gaseste in maximul din aceasta matrice.
Complexitate : O(N * logN *K)
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
