Informatyczny kącik olimpijski

Myszy

Tym razem zajmiemy się zadaniem, które pojawiło się na kolokwium dla studentów pierwszego roku informatyki na Uniwersytecie Warszawskim.

Dla $|k 2$ oraz tablicy
$a 1,5,1,4,3,2,7,0$
poprawnym wynikiem jest 14. Jeden kot może pilnować fragmentu korytarza na metrach od 2 do 4 (łapiąc 6 z 10 myszy), a drugi może pilnować fragmentu na metrach od 5 do 7 (łapiąc 8 z 12 myszy).

W korytarzu harcują myszy. Korytarz ma długość $| n$ metrów. Dana jest tablica $n$ nieujemnych liczb całkowitych $a[]$ opisująca, gdzie jest ile myszy: dla $|1⩽ i⩽ n$ na $i$ -tym metrze korytarza (patrząc od strony wejścia) jest $a[i]$ myszy. Dysponujesz $|k$ kotami $(k ⩽ n).$ Twoim zadaniem jest takie rozmieszczenie kotów w korytarzu, żeby złapały jak najwięcej myszy. Każdy kot może pilnować ustalonego przez Ciebie spójnego fragmentu korytarza (na przykład, może mieć założoną smycz odpowiedniej długości, przymocowaną do podłogi pośrodku pilnowanego fragmentu korytarza). Fragmenty korytarza pilnowane przez różne koty nie mogą zachodzić na siebie (żeby koty się nie pobiły, a smycze nie poplątały), choć mogą się stykać. Niektóre fragmenty korytarza mogą pozostać niepilnowane przez żadnego kota. Kot, który pilnuje fragmentu od $| i$ -tego do $| j$ -tego metra włącznie (dla $| i⩽ j$ ), na którym znajduje się $|s = a[i]+ a[i + 1]+ ⋯ + a[ j]$ myszy, złapie: $2 max(s − ( j− i) ,0)$ myszy. Należy wyznaczyć maksymalną liczbę myszy, jakie mogą złapać koty (patrz rysunek).

Obojętnie, jak zabierzemy się za to zadanie, przyda się nam tablica sum prefiksowych: $s[ j] = P1DiD ja[i].$ Wtedy liczba myszy na fragmencie $|[i, j]$ przedstawia się jako $s[ j]− s[i− 1].$

Omawiane zadanie to zadanie na programowanie dynamiczne. Niech $d[ j,l]$ oznacza maksymalną liczbę myszy, jakie może złapać $l$ kotów na pierwszych $| j$ metrach korytarza. Ponieważ niektóre fragmenty mogą być niepilnowane, więc rekurencję budujemy, rozpatrując dwa przypadki: albo $j$ -ty metr nie jest pilnowany, albo jest i $|l$ -ty kot pilnuje fragmentu $[i, j]$ (od $|i$ -tego do $| j$ -tego metra włącznie):

d[ j,l] = max (d[ j −1,l],max0DiD j(d[i− 1,l− 1]+ s[ j]− s[i −1]− ( j −i)2)).

(*)

Podstawowa implementacja zadziała w czasie $O(n2k).$ Takie było oczekiwane rozwiązanie na kolokwium, niemniej jednak okazało się, że można to zrobić lepiej (ach, ci studenci). Aby przyspieszyć rozwiązanie, należy w odpowiedniej kolejności wypełniać tablicę $|d.$ Główna pętla powinna przebiegać po $l.$ Ustalmy $|l$ i załóżmy, że mamy obliczone wartości $|d[ j,l− 1]$ dla wszystkich $| j.$ Będziemy teraz obliczać element $d[ j,l].$ Kluczem do usprawnienia rozwiązania jest porównanie możliwych dwóch ustawień $|l$ -tego kota, mianowicie gdy patroluje on fragment $[i1, j]$ lub fragment $|[i2, j],$ gdzie $i1 < i2.$ Drugie ustawienie jest lepsze od pierwszego, jeśli:

2 2 d[i1−1,l−1]+s[ j]−s[i1− 1]− ( j− i1) < d[i2−1,l−1]+s[ j]−s[i2− 1]− ( j−i2).

Po przekształceniu nierówność przyjmie postać:

1 j > (d[i1− 1,l− 1] −d[i2 −1,l− 1]− s[i1−1] +s[i2− 1]− i12+ i22)⋅-------. 2(i2− i1)

(**)

Prawa strona nierówności $|(∗∗)$ zależy tylko od $i1$ i $i2$ (oraz od $l$ ); oznaczmy ją przez $|p(i1,i2).$ Widzimy, że pierwsze ustawienie jest lepsze dla $| j$ mniejszych od $p(i1,i2),$ po czym, począwszy od $⌈p(i1,i2)⌉,$ lepsze staje się drugie ustawienie. Ta obserwacja umożliwia przeglądanie możliwych ustawień $l$ -tego kota w sposób bardziej uporządkowany tak, że na bieżąco eliminujemy takie ustawienia, które są już od pewnych $j$ gorsze. Trzymamy kolejkę dwukierunkową początków fragmentów $1⩽ i1 < ⋯ < im< j,$ taką że

j < ⌈p(i1,i2)⌉< ⌈p(i2,i3)⌉ < ⋯ < ⌈p(im ,im)⌉.

Innymi słowy, dla odpowiednio małych $| j$ najlepiej przydzielać $l$ -temu kotu fragment $[i1, j],$ gdy $j$ osiągnie $|⌈p(i1,i2)⌉$ - fragment $[i2, j],$ i tak dalej aż do $j ⩾⌈p(i ,i )⌉, m m$ gdzie optymalny przydział to $[i , j]. m$ Przetwarzanie $| j$ -tego metra korytarza składa się z następujących kroków:

1.: Jeżeli kolejka ma co najmniej dwa elementy oraz $j ⩾⌈p(i1,i2)⌉,$ to usuwamy z przodu kolejki $i , 1$ gdyż od tego momentu lepsze będą fragmenty o początku $i2.$
2.: Jeżeli kolejka ma wciąż co najmniej dwa elementy, to sprawdzamy, czy $|⌈p(i ,i )⌉⩾ ⌈p(i , j)⌉. m m m$ Jeżeli tak, to fragmenty o początku $|i m$ są zdominowane przez fragmenty o początkach $|im$ lub $| j,$ usuwamy więc $im$ z końca kolejki i powtarzamy krok 2.
3.: Dodajemy $j |$ na koniec kolejki.
4.: Obliczamy $d[j, l],$ korzystając ze wzoru $(∗),$ ale możemy to już teraz zrobić w czasie $O(1),$ gdyż wiemy, że maksimum jest osiągane przy $i = i , 1$ gdzie $i 1$ jest aktualnym elementem z przodu kolejki.

W ten sposób otrzymaliśmy rozwiązanie o złożoności czasowej $|O(nk).$