|
Titlul: 2393 Yogurt factory Scris de: Bogdan-Alexandru Stoica din August 24, 2007, 14:16:09 http://acm.pku.edu.cn/JudgeOnline/problem?id=2393
Nu reusesc sa scap de N^2 din urmatoarea recurenta: C[ i ] = costul minim pentru a satisface cererile de la 1 la i. C[ i ] = C[ i-1 ] + MIN(X*C[ j ] + (Y[ i ]-X)*C[ i ] + (i-j)*S), X = 1,Y[ i ] si j = 1,i; nu reusesc ca pentru un X fixat sa aflu intr-o complexitate decenta acel minim. ma bazez pe faptul ca Y[ i ] nu e asa mare precum scrie in enunt :p poate ca exista si alte idei, dar mie nu mi-a venit decat asta... ](*,) Titlul: Răspuns: 2393 Yogurt factory Scris de: Adrian Diaconu din August 24, 2007, 18:42:40 Nu iti mai trebuie sa variezi X-ul ala, adica o sa cumperi tot din acelasi loc.
C[ i ]= C[ i-1 ] + Y[ i ] * MIN ( cost[j] + (i-j)*S ), j=1..i Si bagi un deque si gata. Titlul: Răspuns: 2393 Yogurt factory Scris de: Mircea Pasoi din August 24, 2007, 19:17:34 Avand in vedere ca iaurtul nu se strica, poti sa renunti la deque si sa faci greedy.
Titlul: Răspuns: 2393 Yogurt factory Scris de: Adrian Diaconu din August 24, 2007, 19:21:39 Mda, nu eram atent. Ma gandeam la altceva :-'
Titlul: Răspuns: 2393 Yogurt factory Scris de: Bogdan-Alexandru Stoica din August 27, 2007, 12:53:04 m-am complicat singur. mi s-a parut dubios sa iau totul din acelasi loc. multumesc mult pentru idicatii. :D
Titlul: Răspuns: 2393 Yogurt factory Scris de: Savin Tiberiu din August 27, 2007, 13:20:00 gasesti o varianta putin mai complicata a problemei aici http://infoarena.ro/problema/branza. E acelasi lucru doar ca branza se poate strica.
|