Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 2393 Yogurt factory  (Citit de 24489 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
fireatmyself
Nu mai tace
*****

Karma: 36
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« : 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... Brick wall
Memorat

Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« Răspunde #1 : 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.
« Ultima modificare: August 24, 2007, 18:45:13 de către Adrian Diaconu » Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #2 : August 24, 2007, 19:17:34 »

Avand in vedere ca iaurtul nu se strica, poti sa renunti la deque si sa faci greedy.
Memorat
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« Răspunde #3 : August 24, 2007, 19:21:39 »

Mda, nu eram atent. Ma gandeam la altceva Whistle
« Ultima modificare: August 24, 2007, 19:24:42 de către Adrian Diaconu » Memorat
fireatmyself
Nu mai tace
*****

Karma: 36
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #4 : 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.  Very Happy
Memorat

Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #5 : 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.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines