Omówienie zadania Cukiernia (I etap XXVIII OI)

Rozwiązanie zachłanne

Załóżmy najpierw, że każdy rodzaj wypieków występuje na co najmniej jednej gablocie. Wypiek w danej gablocie nazwiemy dominującym, jeśli jest go tam najwięcej. Wówczas na każdej gablocie możemy w najlepszym razie zostawić tylko wypieki tego rodzaju. Jeśli każdy rodzaj wypieków jest dominujący na co najmniej jednej gablocie, to taki sposób poprzestawiania istnieje i jest optymalny.

Rodzaj wypieku nazwiemy brakującym, jeśli nie jest dominujący na żadnej gablocie. Jeśli dwa rodzaje wypieków są brakujące – powiedzmy pączki i rogaliki – to sprawdzamy, na których gablotach wartość \(d_i-p_i\) i wartość \(d_i-r_i\) jest minimalna. Jeśli to są dwie różne gabloty, to zmieniamy przyporządkowanie tak, żeby to na te gabloty przełożyć, odpowiednio, wszystkie pączki i rogaliki. Jeśli jednak jest to ta sama gablota, to musimy rozważyć second min wartości \(d_i-p_i\) lub \(d_i-r_i\).

Jeśli jeden rodzaj wypieku jest brakujący – powiedzmy rogaliki – a każdy z pozostałych rodzajów wypieków jest dominujący na co najmniej dwóch gablotach, to wybieramy gablotę, dla której \(\max(d_i,p_i)-r_i\) jest minimalne, i to tam umieszczamy rogaliki. Jeśli jednak jeden z rodzajów wypieków jest dominujący na tylko jednej gablocie – powiedzmy pączki na gablocie numer \(j\) – to musimy też rozważyć sytuację, że opłaca się na tej właśnie gablocie wybrać rogaliki, płacąc \(p_j-r_j\), i na jednej z pozostałych gablot \(i \ne j\) wybrać pączki, płacąc \(d_i-p_i\).

Na koniec podobnie obsługujemy przypadek, gdy któryś rodzaj wypieków nie występuje na żadnej gablocie (a jeśli jest tylko jeden rodzaj wypieków, to wynikiem jest 0).

Rozwiązanie działa w czasie \(O(n)\).

Programowanie dynamiczne

Wystarczy wyznaczyć tablicę \(dp[i,mask]\), gdzie \(0 \le i \le n\) i \(0 \le mask < 8\). Tutaj \(dp[i,mask]\) oznacza minimalną liczbę przestawień w gablotach \(1,\ldots,i\), taką że po ich wykonaniu otrzymuje się co najmniej jedną gablotę z dominującym \(j\)-tym rodzajem wypieku (\(j \in \{0,1,2\}\)), dla każdego \(j\) dla którego \(j\)-ty bit w masce jest zapalony.

Obliczanie kolejnych stanów \(dp[i,mask]\) jest dość proste, możemy:

• zostawić wypiek, którego jest najwięcej na półce \(i\) i skorzystać z wyniku \(dp[i-1,mask]\),

• jeśli \(j\)-ty bit w \(mask\) jest zapalony: uczynić \(i\)-tą gablotę składowiskiem wszystkich wypieków typu \(j\); wtedy zostawiamy wypiek \(j\) oraz korzystamy z wyniku \(dp[i-1,mask - 2^j]\).

Złożoność czasowa to również \(O(n)\).

Podzadanie 1

Możemy przeiterować się po wszystkich możliwych wyborach gablot, do których przekładamy pączki, rogaliki i drożdżówki. Dla każdego z \(O(n^3)\) takich wyborów iterujemy się po wszystkich gablotach i obliczamy w czasie \(O(n)\) koszt przełożenia wypieków. Na końcu wybieramy najlepszy koszt.

Złożoność czasowa to \(O(n^4)\).

Rozwiązanie alternatywne

Powyższe rozwiązanie brutalne można też przyspieszyć do liniowego. Jedyną różnicą jest to, że wybieramy sobie maksymalnie \(9\) gablot, na których będziemy próbować rozmieszczać poszczególne wypieki. Dla każdego wypieku z osobna znajdujemy trzy najlepsze dla niego gabloty (czyli takie, na których najmniej płacimy wyrzucając pozostałe wypieki).

Zauważmy, że rozwiązanie zachłanne robi podobną rzecz: ,,spycha” wypieki na drugą najlepszą lub trzecią najlepszą dla tego wypieku gablotę i wybiera najtańsze ustawienie.