programowanie dynamiczne, zadanie kieszonkowe OIG

Question

Chcąc przećwiczyc dp, natknąłem się na takie zadanie z OIG: https://szkopul.edu.pl/problemset/problem/PJA7VC3zOTwh1qPU43Wu9O4v/site/?key=statement

3 razy próbowałem napisać zachłana, ale wszystkie trzy się wywaliły, ale napisałem dp na 40pkt, w O(N*K). Mianowicie: dp[i][j] - max wynik, jaki możemy osiągnąć przeglądając stosiki od 0 do i, biorąc dokładnie j elementów.

A - tablica górnych elementów

B - tablica dolnych elementów

    dp[0][1] = A[0];
    dp[0][2] = A[0] + B[0];
    for (int i = 1; i < n; ++i)
    {
        dp[i][1] = max(dp[i-1][1], A[i]);
        dp[i][2] = max(dp[i-1][2], max(dp[i-1][1] + A[i], A[i] + B[i]));
        for (int j = 3; j <= k; ++j)
            dp[i][j] = max(dp[i-1][j], max(dp[i-1][j-1] + A[i], dp[i-1][j-2] + A[i] + B[i]));
    }

No i na koniec zwracam dp[n-1][k].

No i mam problem, jak to przyśpieszyć, o ile się wogóle da. 

Z góry dziękuję za pomoc i poświęcony czas!

Comments

Często oznaczasz tablice "dp" i często używasz tego skrótu w opisach. Co on oznacza? Mnie DP kojarzy się z dynamic programming. Zgadłem?

---

Dokładnie dp, piszę jak używam dynamika, i zazwyczaj jest to tablica / vector, która służy do liczenia wartości w dynamiku.

Answer 1

Na pewno algorytm zachłanny. Przypomina mi to zadania z CF Div B, trzeba szybko zrobić kilka obserwacji, uwierzyć swojej intuicji że wymyślony algorytm działa, zaimplementować i zobaczyć czy przejdzie. No więc mam pomysł, ale trzeba go przetestować.

Najlepiej by było oczywiście brać największe monety. Więc posortujmy monety, znajdźmy K największych i bierzmy je ze stosu o ile są na górze (lub któraś ze wcześniej wziętych monet odblokowała tą na dole). Teraz jeśli wzieliśmy L monet to pozostałe K-L największych monet musi być na dole stosu, więc żeby je wydobyć musimy skorzystać z 2 ruchów. Ale może zamiast tego opłaca nam się wziać 2 monety które lezą już same na stosie. Więc musimy posortować po sumie wszystkie pary 2 "wolnych" monet i pary monet z pełnego stosu i wybierać największe.

Comments

W sumie jak tak teraz myśle to ta druga faza, gdy sortujemy po sumie 2 monet może być błędna. Ale pierwsza, czyli ta w której bierzemy K największych monet na pewno jest poprawna. Wzorcówka na pewno będzie działała jakoś podobnie

---

Chodzi Ci mniej więcej o to, że mamy 2 sety, jeden set, nazwijmy go pojedyńczym, i przechowuje te co możemy wziąć z góry, i na początku wrzucamy na niego wszystkie N elementów z górnej cześci każdego stosu. I mamy też drugi set, nazwijmy go podwójnym i na niego wrzucamy, sumę elementów z górnego i dolnego częsci stosu. Oba maja na starcie N elementów.  I teraz jak sprawdzamy, to  sprawdzamy, czy suma dwóch największych z pojedyńczego jest > od największego z podwójnych. Jak jest większa, to bierzemy te 2 elementy, dodajemy do wyniku i dolne z tych co wzieliśmy wrzucamy spowrotem na seta, a jak nie to pożeramy te z podwójnego, i z każdym obiegiem zmniejszamy licznik ile mamy do zdjęcia o 2?

---

Tak, ale to jest ta 2. faza. Na początku trzeba zrobić pierwszą. Tylko teraz wydaje mi się, że to nie będzie jednak działać poprawnie

---

znalazłem jeden test, który był złośliwy, i psuł mi wszystkie 3 zachłany jakie napisałem do tej pory:

5 4
5 1 2 5 1
1 1 6 4 5

---

@Whistleroosh, 

Ja miałem jeszcze 2 pomysły

1 - Do jakiegoś momentu zrobić zachłana, a jak zostanie mało to puścić dynamika

2 - Symulować kolejno min wyn, biorąc 0 razy oba elementy, 1 raz oba elementy, 2 razy oba elementy, 3 razy oba elementy... aż do k / 2.

---

Hmm, ten drugi pomysł brzmi dobrze. wtedy trzeba tylko umieć zsumować szybko k - 2 * ile_wzielismy_stosow najwiekszych elementów z góry stosu

---

Znalazłem rozwiązanie na YT https://www.youtube.com/watch?v=hhrLaokKBtk, i faktycznie pomysł opiera się mniej więcej na takim zachłanie co mysleliśmy, tylko trochę innaczej trzeba podejść.

Pomysł jest taki, że jeśli A, oznacza tablicę na górnych stosach, a B dolnych, to dla każdego i, jesli A[i] >= B[i], to dodajemy na vector pojedyńczych. Bo zauważamy, że jeśli górny jest większy niż dolny, to zawsze weźmiemy górny jako pierwszy, bo jest większy, a jeśli A[i] < B[i], to wrzucamy na vector podwójnych, w sensie bierzemy ich sumę i wrzucamy na drugi vector. Oba vectory sortujemy od największych, i teraz odtwarzamy wyniki biorąc 0 elementów z vectora pojedyńczych, k z vectora podwójnych, potem 1 z pojedyńczych i k-1 z podwójnych, 2 z pojedyńczych, k-2 z podwójnych, 3 z pojedyńczych, k-3 z podwójnych....... i tak aż do k z pojedyńczych i 0 z podwójnych. Jeśli chodzi na pojedyńcze, to schemat jest prosty, zawsze opłaca nam się wziąc od jak największych. I teraz to czego mi brakło to lemat, jak robić to z podwójnymi. Lemat mówi tak: jeżeli bierzemy z podwójnych G elementów, to jeśli G jest parzyste, to zawsze bierzemy sumę z pierwszych G / 2 stosów (G / 2, bo to są sumy podwójnych), a jeśli G jest nieparzyste, to bierzemy max(suma pierwszych G / 2 + największa wartośc na pojedyńczym stosie na prawo od G / 2, na lewo od G / 2, suma pierwszych (G / 2 + 1) - min z pojedyńczego na lewo, czyli w przedziale od 0 do (G / 2)).

No i złożonność to O(N lg N), bo trzeba posortować oba vectory.

Kod dający 100: 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

struct Element
{
    int suma;
    int gorny;
    int dolny;
    bool operator < (const Element &element) const
    {
        return suma > element.suma;
    }
};

int n = 0, k = 0, wczytana_liczba = 0, maxx = 0;
ll wyn = 0, suma = 0;
vector<int> A;
vector<int> B;
vector<int> pojedyncze;
vector<Element> podwojne;
vector<ll> dp_podwojne;
vector<int> maxy_sufixowe;
vector<int> miny_prefixowe;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;

    A.assign(n,0);
    B.assign(n,0);
    for (int i = 0; i < n; ++i)
        cin >> A[i];
    for (int i = 0; i < n; ++i)
        cin >> B[i];

    for (int i = 0; i < n; ++i)
    {
        if (A[i] >= B[i])
        {
            pojedyncze.push_back(A[i]);
            pojedyncze.push_back(B[i]);
        }
        else
            podwojne.push_back({A[i] + B[i], A[i], B[i]});
    }

    sort(pojedyncze.begin(), pojedyncze.end(), greater<ll>());
    sort(podwojne.begin(), podwojne.end());

    dp_podwojne.assign((2*n)+1,0);

    if (podwojne.size() > 0)
    {
        maxy_sufixowe.assign(podwojne.size(),-1e9-20);
        miny_prefixowe.assign(podwojne.size(),1e9+20);

        maxy_sufixowe[podwojne.size()-1] = podwojne[podwojne.size()-1].gorny;
        for (int i = podwojne.size()-2; i >= 0; --i)
            maxy_sufixowe[i] = max(podwojne[i].gorny, maxy_sufixowe[i+1]);

        miny_prefixowe[0] = podwojne[0].dolny;
        for (int i = 1; i < podwojne.size(); ++i)
            miny_prefixowe[i] = min(podwojne[i].dolny, miny_prefixowe[i-1]);

        dp_podwojne[1] = maxy_sufixowe[0];
    }

    for (int i = 2; i <= podwojne.size() * 2; ++i)
    {
        if (i % 2 == 0)
        {
            suma += podwojne[i/2-1].suma;
            dp_podwojne[i] = suma;
        }
        else
            dp_podwojne[i] = suma + max(maxy_sufixowe[i/2],podwojne[i/2].suma - miny_prefixowe[i/2-1]);
    }

    suma = 0;
    int do_kiedy = min(k,(int)pojedyncze.size());
    for (int i = 0; i <= do_kiedy; ++i)
    {
        wyn = max(wyn, suma + dp_podwojne[k-i]);
        suma += pojedyncze[i];
    }

    cout << wyn << '\n';

    return 0;
}

Ciekawi mnie, to że powiedzieli, że istnieje wiele rozwiązań tego zadania. Ciekawi mnie czy da się jakoś dp napisać. Zadanie trudne jak na OIG-a. Ale zadanie bardzo fajne, podobało mi się.

---

Da się pewnie też zrobić drzewem przedziałowo-licznikowym. Wystarczy żeby drzewo umiało odpowiadać na zapytania: "który element jest k-ty największy" i suma na przedziale. Wartości są w do 1e9 więc albo trzeba korzystać z dynamicznego drzewa albo kompresować. Jak mamy taką strukturę to mozemy zrobić to od tej drugiej strony, czyli wybieramy ile pełnych stosów bierzemy i potem dopełniamy pojedynczymi. Ale to co zapisałeś jest bardziej eleganckie