Na początku należało zauważyć dość intuicyjną sprawę: Hektor w każdym momencie powinien uczyć się do najbliższego (pod względem terminu) sprawdzianu do którego jeszcze nie jest w pełni przygotowany.
Posortujmy sprawdziany Hektora jak powyżej.
Niech:
- czas_na_przygotowanie[k] oznacza czas potrzebny na przygotowanie do k-tego sprawdzianu
- suma_czasu_na_przygotowanie[k] oznacza sume czasu potrzebną na przygotowanie do pierwszych k egzaminów
- przygotowanie_do_pierwszych[k] oznacza na ile dni przed pierwszym egzaminem Hektor musi zacząć się uczyć aby nauczyć się do pierwszych k egzaminów
Wartościa jaką szukamy jest przygotowanie_do_pierwszych[N]
Zastanówmy się jak obliczyć przygotowanie_do_pierwszych[k]:
1) Gdy k-ty sprawdzian jest conajmniej czas_na_przygotowanie[k] dni po (k-1)-szym sprawdzianianie to Hektor uczy się na pierwsze k-1 sprawdzianów a później uczy się na k-ty sprawdzian: wynik to przygotowanie_do_pierwszych[k-1].
2) Gdy k-ty sprawdzian jest conajmniej czas_na_przygotowanie[k]+czas_na_przygotowanie[k-1] dni po (k-2)-gim sprawdzianie to Hektor uczy się na pierwsze k-2 sprawdzianów a następnie uczy się na 2 pozostałe egzaminy. wynik to przygotowanie_do_pierwszych[k-2].
(...)
k) Gdy Hektor może do wszystkich k-egzaminów uczyć się bez przerwy kończąc w dniu k-tego egzaminu to wynik wynosi data_egzaminu[1]-data_egzaminu[k]+suma_czasu_na_przygotowanie[k]
Zauważmy, że przygotowanie_do_pierwszych[k] to maksimum z wyników z powyższych przypadków(nie może być mniej ponieważ Hektor musi nauczyć się na czas na pierwsze m egzaminów dla każdego m<k, oraz musi się uczyć conajmniej suma_czasu_na_przygotowanie[k]).
Gdyby liczyć wynik z podanej powyżej definicji algorytm wyglądałby następująco:
for(int k=1; k<=N; k++)
for(int j=1; j<=k; j++)
przygotowanie_do_pierwszych[k] = max(przygotowanie_do_pierwszych[k],wynik dla przypadku k-tego)
Niestety jest to algorytm kwadratowy.
Łatwo zauważyć, że przygotowanie_do_pierwszych[N] to maksymalny wynik spośród wszystkich analizowanych przypadków.
Popatrzmy jakie czynniki wchodzą w skład wyników przypadków prócz wartości z tablicy przygotowanie_do_pierwszych.
Są to tylko wyniki z przypadków typu: "Gdy Hektor może wszystkich k-egzaminów uczyć się pod rząd kończąc w dniu k-tego egzaminu to wynik wynosi data_egzaminu[1]-data_egzaminu[k]+suma_czasu_na_przygotowanie[k]" (przypadki te nazywać będę dla uproszczenia przypadkami bazowymi)
Ponieważ wszystkie wyniki są obliczane na podstawie przypadków bazowych wystarczy wziąść maksimum z wyników dla tych przypadków.
Tych przypadków jest N i są one obliczane w czasie stałym więc złożoność jest O(N).
Zatem obliczanie wyniku to:
wynik=0;
for(int k=1; k<=N; k++)
wynik = max(wynik, data_egzaminu[1]-data_egzaminu[k]+suma_czasu_na_przygotowanie[k]);