7. Improvizovaná akrobacia vzorové riešenie

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

5

Naivná dynamika

Definujeme \(dp[i][j]\) ako maximálny počet spojení, ak posledná dvojica, ktorú sme vybrali je \((i, j)\) (príslušné čísla stromov sú \((p_i, q_j\))). Ak dvojicu \((i, j)\) nie je možné vybrať (\(|p_i-q_j| > 4\)), definujeme \(dp[i][j]\) ako \(0\). Teraz je odpoveď jednoducho maximum \(dp[i][j]\) spomedzi všetkých \((i, j)\).

Ako spočítať \(dp\)? Prejdeme vzostupne všetky \(i\) od \(1\) po \(n\) a pre každé \(i\) prejdeme všetky \(j\) od \(1\) po \(n\). Ak \(|p_i-q_j| > 4\), tak \(dp[i][j] = 0\). Inak vyskúšame všetky možné predošlé dvojice, teda \((k, l)\) také, že \(k < i, l < j\). Odpoveď je jednoducho \(dp[i][j] = 1+ \max \lbrace dp[k][l] \rbrace\). Časová zložitosť je \(O(n^4)\) (máme \(n^2\) stavov a každý spracujeme v \(O(n^2)\)).

Vylepšená dynamika

Dvojice \((i, j)\), ktoré spĺňajú \(|p_i - q_j| \leq 4\) volajme validné. Všimnime si, že validných dvojíc je v skutočnosti málo. Pre každé \(i\) je ich najviac \(9\), celkovo teda \(O(n)\). To znamená, že vieme vyššie popísaný algoritmus vylepšiť hneď dvoma spôsobmi: - môžeme zredukovať počet stavov v našom dynamickom programovaní – stačia nám stavy zodpovedajúce validným dvojiciam; - pri počítaní \(dp\) nám stačí kontrolovať menej možných predošlých dvojíc.

Na začiatku si vygenerujeme všetky validné spojenia. Toto vieme spraviť v čase \(O(n)\) (napríklad priamočiaro za pomoci poľa \(q_{inv}\) takého, že \(q_{inv}[q_j] = j\).) Validné spojenia si očíslujeme od \(1\) po \(S\). Pre \(s \in \lbrace 1, \dots, S\rbrace\) definujeme \(dp[s]\) ako najväčší počet spojení, ktorý vieme dosiahnuť, ak posledné vybrané spojenie je \(s\).

Ako spočítať \(dp\)? Prechádzame cez všetky validné spojenia s číslom \(\tilde{s} \in \lbrace 1, \dots, S \rbrace\). Skontrolujeme, či je spojenie \(\tilde{s}\) naľavo od \(s\) (ak spojeniu \(s\) zodpovedá \((i, j)\) a spojeniu \(\tilde{s}\) zodpovedá \((\tilde{i}, \tilde{j})\), tak kontrolujeme, či \(\tilde{i} < i\) a zároveň \(\tilde{j} < j\) ). Potom \(dp[s] = 1 +\) maximum z príslušných hodnôt \(dp[\tilde{s}]\). Časová zložitosť sa zlepšila na \(O(n^2)\) (máme \(O(n)\) stavov a každý spracujeme v \(O(n)\)).

Vzorová dynamika

Kľúč k úspechu je zapracovať na počítaní \(dp[s]\) pre konkrétne \(s\). Validné dvojice budeme prechádzať v zotriedenom poradí, po skupinkách: najprv spracujeme tie, ktoré majú \(i = 1\), potom tie s \(i = 2\), atď. Vďaka tomuto bude jednoduché overovať, či \(\tilde{i} < i\). Pri počítaní \(dp[s]\) potrebujeme preveriť všetkých kandidátov na predošlú dvojicu. Kto sú reálni kandidáti? Sú to presne všetky validné dvojice \(\tilde{s}\) s \((\tilde{i}, \tilde{j})\) z predošlých skupiniek (\(\tilde{i} < i\)), pre ktoré \(\tilde{j} < j\). Potrebujeme zobrať maximum z hodnôt \(dp[\tilde{s}]\) pre týchto kandidátov. Na takéto veci je ako stvorený intervalový strom.

Vytvoríme si intervaláč, v ktorom si pre fixné \(\tilde{j}\) od \(1\) po \(n\) budeme udržovať maximálne \(dp[\tilde{s}]\) pre validné dvojice \(\tilde{s}\) zodpovedajúce \((\tilde{i}, \tilde{j})\) pre \(\tilde{s}\) zo skupiniek, ktoré sme už spracovali. (Ak teda práve spracovávame skupinku s nejakým fixným \(i\), tak hodnota v intervaláči pre fixné \(\tilde{j}\) bude maximum z hodnôt \(dp\) pre validné dvojice spomedzi \((1, \tilde{j}), \dots, (i-1, \tilde{j})\)). Intervaláč budeme updatovať vždy po spracovaní celej skupinky. Takýchto updatov bude po každej skupinke najviac \(9\) (toľko najviac dvojíc je v jednej skupinke) a intervaláč ich vykoná v \(O(\log n)\). No a pri spracovaní konkrétnej dvojice \(s\) zodpovedajúcej \((i, j)\) nám vlastne stačí spočítať maximum hodnôt na intervale \([0, j-1]\). Takéto otázky nám intervaláč zodpovie tiež v \(O(\log n)\).

Celková časová zložitosť tak bude \(O(n \log n)\) (prejdeme \(O(n)\) skupiniek, každú spracujeme v \(O(\log n)\)). Pamäťová zložitosť bude \(O(n)\).

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define FOR(i, x) for(auto &i : x)
#define pb push_back

struct Intervalac {
    int offset;
    vector<int> pole;

    Intervalac(int N) {
        offset = 1;
        while(offset <= N) offset *= 2;
        pole.resize(2*offset, 0);
    }

    void update(int poz, int hod) {
        int v = poz+offset;
        while(v != 0) {
            pole[v] = max(pole[v], hod);
            v /= 2;
        }
        return;
    }

    int maxi(int a, int b, int v, int l, int r) {
        if(l >= b || r <= a) return 0;
        if(a <= l && r <= b) return pole[v];
        return max(maxi(a, b, 2*v, l, (l+r)/2), maxi(a, b, 2*v+1, (l+r)/2, r));
    }

    int maxi(int a, int b) {
        return maxi(a+offset, b+offset, 1, offset, 2*offset);
    }
};

int main() {
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> poz(N);
    REP(n, 0, N) {
        int id;
        cin >> id;
        id--;
        poz[id] = n;
    }
    Intervalac Inter(N);
    int vys = 0;
    REP(n, 0, N) {
        int id;
        cin >> id;
        id--;
        vi hrany, hod;
        REP(jd, max(0, id-4), min(N, id+5)) hrany.pb(jd);
        FOR(jd, hrany) {
            hod.pb(1+Inter.maxi(0, poz[jd]));
            vys = max(vys, hod.back());
        }
        REP(i, 0, hrany.size()) {
            int jd = hrany[i];
            Inter.update(poz[jd], hod[i]);
        }
    }
    cout << vys << "\n";
    return 0;
}