2393 Yogurt factory

[•fireatmyself]

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...

[•DITzoneC]

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.

[•domino]

Avand in vedere ca iaurtul nu se strica, poti sa renunti la deque si sa faci greedy.

[•DITzoneC]

Mda, nu eram atent. Ma gandeam la altceva

[•fireatmyself]

m-am complicat singur. mi s-a parut dubios sa iau totul din acelasi loc. multumesc mult pentru idicatii. 

[•devilkind]

gasesti o varianta putin mai complicata a problemei aici http://infoarena.ro/problema/branza. E acelasi lucru doar ca branza se poate strica.