Pagini recente » Diferente pentru ciclu-hamiltonian-in-graf-dens intre reviziile 11 si 10 | Diferente pentru planificare/sedinta-20080303 intre reviziile 9 si 8 | Diferente pentru autumn-warmup-2007/runda-2 intre reviziile 11 si 10 | Diferente pentru runda/oji_go_11_12 intre reviziile 3 si 1 | 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.
