Kieszonkowe

Dzisiejsze zadanie pochodzi z VIII. Olimpiady Informatycznej Gimnazjalistów w roku szkolnym 2013/2014.

Zadanie. Danych jest $|n$ stosów, ponumerowanych od $|1$ do $|n.$ Każdy stos zawiera dokładnie dwie monety, ułożone jedna na drugiej. Ciąg $|g1,g2,...,gn$ oznacza nominały monet, znajdujących się na górze kolejnych stosów, zaś ciąg $d1,d2,...,dn$ nominały monet, znajdujących się na dole kolejnych stosów. Staś, bohater zadania, może wykonać co najwyżej $|k$ ruchów. W każdym ruchu chłopiec wybiera dowolny niepusty stos i zabiera monetę ze szczytu tego stosu. Jaki jest największy możliwy zysk Stasia?

Rozwiązanie dynamiczne. Zadanie możemy rozwiązać, korzystając z metody programowania dynamicznego. Niech $P[i][ j] D$ oznacza maksymalny zysk dla problemu ograniczonego do stosów o numerach od $1$ do $|i$ oraz maksymalnej liczbie ruchów równej $| j.$ Łatwo obliczyć wartości $PD$ dla pierwszego stosu $(i = 1)$ :

$P[1][0]=0 D$ ;
$P[1][1]=g D 1$ ;
$P[1][ j]=g1+d1, D$ dla $j > 1.$

Przejdźmy teraz do obliczenia wyników dla większej liczby stosów. Dla każdego $|i∈ {2,3,...,n}$ oraz $j∈ {0,1,...,k}$ aby obliczyć wartość $P[i][ j],D$ należy rozpatrzyć trzy sytuacje:

nie bierzemy ani jednej monety z $i$ -tego stosu, wtedy wynikiem jest $P[i−1][ j] D$ ;
bierzemy jedną monetę z $i$ -tego stosu, wtedy wynikiem jest $P[i−1][ j−1]+gi D$ ;
bierzemy dwie monety z $i$ -tego stosu, wtedy wynikiem jest $P[i−1][ j−2]+g+d. D ii$

Wartością $P[i][ j] D$ jest maksimum z trzech powyższych wartości. Oczywiście, druga sytuacja jest możliwa tylko dla $j > 0,$ podobnie trzecia tylko dla $| j > 1.$ Największym zyskiem Stasia jest $P[n][k]. D$

Wszystkich stanów jest $O(nk).$ Obliczenie wyniku dla każdego stanu odbywa się w czasie stałym. Stąd złożoność czasowa rozwiązania wynosi $|O(nk).$

Rozwiązanie zachłanne. Okazuje się, że istnieje rozwiązanie o lepszej złożoności czasowej. Na początku podzielmy stosy na dwie grupy. Niech pierwsza grupa zawiera stosy, których górna moneta ma nominał nie mniejszy niż dolna moneta, nazwijmy je $A$ -stosami. Pozostałe stosy niech tworzą drugą grupę i nazwijmy je $B$ -stosami. Każdą z tych grup rozważmy oddzielnie.

Przypadek 1: $A | stosy.$ Załóżmy, że mamy $|mA$ -stosów. Chcemy wybrać $x$ monet, których sumaryczna wartość jest największa. Załóżmy dodatkowo, że w każdym ruchu możemy wybrać dowolną monetę (górną lub dolną). Nietrudno zauważyć, że aby zmaksymalizować zysk, należy wybrać $x$ monet o największym nominale. Zatem posortujmy wszystkie monety malejąco według nominału. Otrzymujemy ciąg $a1,a2,...,a2m,$ oznaczający wartości wszystkich monet. Największy zysk uzyskamy, jeśli weźmiemy następujące monety: $|a,a ,...,a . 1 2 k$

Strategia zachłanna, która została opisana powyżej, jest również poprawna bez dodatkowego założenia o braniu dowolnej monety. Ustalamy zatem, że możemy brać tylko monety ze szczytu stosu. Przypuśćmy, że w optymalnym rozwiązaniu chcemy wziąć dwie monety $|ai$ (górną) i $|a j$ (dolną), które tworzą jeden stos. Skoro rozważamy $A$ -stos $(ai | ⩾ a j)$ oraz ciąg $|a$ jest posortowany malejąco, to $i⩽ j.$ Zatem strategia zachłanna jest poprawna, ponieważ najpierw wybierze górną monetę $|ai,$ a dopiero potem dolną $aj .$ Tutaj jest drobna subtelność, jeśli dwie monety mają ten sam nominał, wtedy pierwszeństwo ma górna.

Przypadek 2: $|B$ Załóżmy, że mamy $|mB$ -stosów. Chcemy wybrać $|x$ monet, których sumaryczna wartość jest największa. Przypuśćmy, że w optymalnym rozwiązaniu istnieją dwa stosy (o numerach $i$ oraz $j$ ), z których zabieramy po jednej monecie. Bez straty ogólności możemy założyć, że $gi ⩽gj .$ Wiadomo (z własności $B$ -stosu), że $g j < dj .$ Skoro $|gi⩽ g j$ oraz $gj < d j,$ to $gi < d j.$ Zatem wzięcie po jednej monecie ze stosów $|i$ i $| j$ nie jest optymalnym rozwiązaniem, gdyż bardziej opłaca się wziąć dwie monety z $j$ -tego stosu. Stąd otrzymujemy, że w optymalnym rozwiązaniu nie ma dwóch stosów, z których zabieramy po jednej monecie. Innymi słowy, jest co najwyżej jeden stos, z którego zabieramy jedną monetę.

Zatem posortujmy stosy według malejącej sumy nominałów. Otrzymujemy ciąg $|s,s ,...,s, 1 2 n$ gdzie $|s i$ oznacza sumę nominałów $i$ -tego najcenniejszego stosu. Jeśli $|x$ jest parzyste, to wybieramy monety ze stosów $|s1,s2,...,sx2.$ W przeciwnym przypadku rozważamy dwie sytuacje. Pierwsza z nich polega na wzięciu stosów $|s1,s2,...,sx 2$ oraz monety o największym nominale spośród szczytów pozostałych stosów. Druga zaś polega na wzięciu stosów $|s1,s2,...,sx2+1$ bez monety o najmniejszym nominale spośród spodów wybranych stosów.

Podsumowanie. Rozwiązanie opiera się na rozpatrzeniu dla każdego $|x∈ {0,1,...,k}$ następującego przypadku: wybieramy $x$ monet z $|A$ -stosów oraz $k | − x$ monet z $B$ -stosów. Wynikiem jest maksimum spośród wyników dla tych przypadków. Całe rozwiązanie działa w czasie $|O(n$ Szczegóły implementacyjne pozostawiam Czytelnikowi jako ćwiczenie.