„Bilet” – omówienie (spójny podciąg o maksymalnej sumie)

O co chodzi w zadaniu?

Jest n miast. Przez wszystkie miasta prowadzi piaszczysta droga jednokierunkowa; na odcinkach tej drogi pomiędzy miastami, Bajtazar sprzedaje swoje towary, na których zyskuje bądź traci. Bajtazar chce się dostać z pierwszego do ostatniego miasta. Ma on również możliwość wsiąść raz w pociąg, który zabierze go do dowolnego innego miasta (również do poprzedniego). Chcemy obliczyć maksymalny zysk Bajtazara.

Jak się do tego zabrać?

Gdyby Bajtazar nie miał możliwości jednokrotnego użycia pociągu, to musiałby przejść przez wszystkie miasta piaszczystą drogą. Co z kolei oznacza, że wynikiem byłaby suma wszystkich zysków i strat. Oznaczmy zbiór odcinków piaszczystej drogi, jako zbiór liter:

a  b  c  d  e  f  g

Do czego sprowadza się użycie pociągu? Do wzięcia jakiegoś podciągu piaszczystej drogi, np. [a  b],    [d  e  f],    [b  c  d  e] i wykonania jednej z dwóch operacji:

  1. Przedłużenia piaszczystej drogi o ten odcinek (cofnięcie się).
  2. Skrócenia piaszczystej drogi o ten odcinek (pojechanie dalej).

Naszym zadaniem jest znalezienie dwóch podciągów: jednego o maksymalnej sumie, drugiego o minimalnej sumie. Ten o maksymalnej sumie będzie oznaczać dodatkową drogę, którą chcemy jeszcze pokonać. Ten o minimalnej, będzie oznaczać drogę, którą chcemy pominąć. Wynikiem końcowym będzie większa wartość z dwóch wariantów:

  1. Suma całej piaszczystej drogi pomniejszona o minimalny podciąg.
  2. Suma całej piaszczystej drogi powiększona o maksymalny maksymalny podciąg.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

*