Chomik (omówienie)

07.03.2010

Na początku należało zauważyć, że istnieje optymalne rozwiązanie w którym chomikowi podaje się pokarmy w kolejności posortowanej niemalejąco względem czasu ważności.

Po prostu gdy w jakimś rozwiązaniu tego problemu, używamy jakiejś pary pokarmów w odwrotnej kolejności niż niemalejąco względem czasu ważności, to zamiana miejscami tych 2 pokarmów w harmonogramie jedzenia nie zmieni wyniku ani nie sprawi, że jakieś jedzenie będzie jedzone po jego dacie przeterminowania.


W takim wypadku problem można rozwiązać dynamicznie:

dp[i] - maksymalna możliwa suma jakości posiłków po i dniach

for(int i=0; i<=N; i++){
    fnp = czas_waznosci_posilku[i]
    maxx = na_ile_dni_starczy_posilek[i];
    value = jakosc_posilku[i];
       
    for(int i=fnp; i>=1; i--) dp[i]=maksimum z
        dp[i], //nie korzystamy z tego pokarmu
        dp[i-1]+value, // korzystamy z pokarmu przez 1 dzień
        ...
        dp[i-maxx]+value*maxx, // korzystamy z pokarmu przez maxx dni
}

Jedyny problem to szukanie maksimów.
Niestety brutalne rozwiązanie szukania maksimów (pojedynczym forem) daje złożoność całego algorytmu O(N*M^2).

Da się to przyśpieszyć. Kod
for(int i=fnp; i>=1; i--) dp[i]=maksimum z
    dp[i], //nie korzystamy z tego pokarmu
    dp[i-1]+value, // korzystamy z pokarmu tylko w 1 dzień
    ...
    dp[i-maxx]+value*maxx, // korzystamy z pokarmy m dni
   
w rozwiązaniu wzorcowym działa w czasie O(M).

W tym celu tworzy się kolejke potencjalnych maksimów.
Potencjalne maksimum, to element który ma jeszcze szanse zostać kiedyś maksimum.
Elementy w kolejce zawsze są w kolejności niemalejącej względem aktualnej wartości.

Zasade działania takiej kolejki najłatwiej zrozumieć na podstawie jej kodu.

//deq to kolejka dwustronna, istnieje w stlu jako deque
for(int i=0; i<=fnp; i++){
    if (i-maxx-1 == deq.front().dzienDodania)
        deq.pop_front(); //jesli dzień najlepszego potencjalnego maksimum to i-maxx-1
                              //to takiego elementu nie możemy już używać
                              //(nie starczy na tyle dni aktualnego posiłku)
    //Ten kod gwarantuje, że nie użyjemy posiłku dłużej niż przez maxx dni.
    
                    
    while(!deq.empty() && porownaj(i,deg.front())) // dopoki kolejka nie jest pusta
                          //i dodanie nowego elementu sprawia, że ostatnie potencjalne maksimum
                          //przestaje być potencjalnym maksimum
         deq.pop_back(); //usuń ostatnie potencjale maksimum
    
    //Ten kod gwarantuje, że z kolejki zostaną usunięte elementy
    // które przestają być potencjalnymi maksimami.
    
    deq.PB(i); //dodaj nowe potencjalne maksimum
    NOWE_DP[i]=STARE_DP[deq.front().dzienDodania] + (i-deq.front().dzienDodania)*value;
}
STARE_DP = NOWE_DP

Całe rozwiązanie ma złożoność O(N*M).

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com