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