Nu aveti permisiuni pentru a descarca fisierul grader_test10.ok
Diferente pentru deque-si-aplicatii intre reviziile #56 si #57
Nu exista diferente intre titluri.
Diferente intre continut:
h3. Soluţie:
Să o rezolv întâi...
Voi face un desen pentru explicaţii. :) == code(cpp) | Algoritmul este: // S[] şirul iniţial de numere iar N lungimea sa // (last, i] este intervalul de lungime maximă care se termină în i a cărui sumă nu depăşeşte M sum = 0; last = 0; // indicii head si tail ai dequeului deque[head = tail = 1] = 0; pentru i = 1, N execută sum += S[i]; temp = bst[ deque[tail] ]; cât timp (head <= tail) şi S[ deque[tail] ] <= S[i] execută temp = Min(temp, iMin[tail]); tail --; sfcâttimp // adaug poziţia i la deque tail ++; deque[tail] = i; // actualizez iMin[] iMin[tail] = temp; // actualizez T[] update(T, tail, iMin[tail] + S[i]); cât timp (head <= tail) şi (sum > M) execută sum -= S[last]; dacă (deque[head] == last) atunci head ++ sfdacă iMin[head] = query(bst, last, deque[head] - 1); update(T, head, M[head] + S[ deque[head] ]); last ++; sfcâttimp // reţin optimul pentru poziţia curentă bst[i] = query(T, head, tail); sfpentru scrie bst[N]; Sfârşit. ==
h3(#problema-6). Problema 6: 'Bcrc':problema/bcrc (Stelele Informaticii 2006)