Sprawdziany (omówienie)

03.03.2010

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:

  1. czas_na_przygotowanie[k] oznacza czas potrzebny na przygotowanie do k-tego sprawdzianu
  2. suma_czasu_na_przygotowanie[k] oznacza sume czasu potrzebną na przygotowanie do pierwszych k egzaminów
  3. 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]);

Organizatorzy:

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com