4. Zápolenie o cukríky vzorové riešenie

5 3
1 2 3 3 2
3 7 1
2

11

Riešenie hrubou silou

Ako pri väčšine úloh, aj pri tejto sa dá vcelku ľahko vymyslieť riešenie, ktoré vyskúša všetky možnosti zjedenia cukríkov, vypočíta chutnosť každej podpostupnosti a vypíše najväčšiu z nich.

Vezmime si prvý cukrík. Ten v našej výslednej postupnosti buď bude, alebo nebude. Zrátame teda akú najväčšiu chutnosť môže dosiahnuť zvyšok postupnosti ak tento prvý cukrík vezmeme a ak ho nevezmeme, a vyberieme z nich tú lepšiu možnosť. Spravíme si teda rekurzívnu funkciu rek, ktorá dostane ako parametre pozíciu momentálne spracovávaného cukríka v postupnosti a typ posledného zjedeného cukríka. Funkcia pomocou samej seba (rekurzívne) spočíta dve hodnoty – chutnosť zvyšku postupnosti podľa toho či momentálne spracovávaný cukrík v postupnosti bude alebo nie – a vyberie možnosť s najväčšou chutnosťou. Maximálnu chutnosť vráti ako výstup. Na výpočet celej úlohy potom stačí zavolať rek na prvý cukrík s tým, že predtým nebol zjedený žiaden iný a vypísať hodnotu, ktorú vráti.

Už len odhadneme časovú zložitosť takéhoto riešenia. Pre každý cukrík máme dve možnosti, čo s ním spraviť, zjeme ho alebo ho nezjeme. Všetkých možností, ako vybrať niekoľko cukríkov je preto \(2^n\), čo bude aj časová zložitosť nášho riešenia – \(O(2^n)\).

Za takéto riešenie bolo možné získať 1 bod.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector <int> cukriky;
vector <int> chutnost;
int cena_nova;

int rek (int pozicia_aktualneho, int typ_predosleho) {
    // už sme pojedli všetky cukríky
    if (pozicia_aktualneho == cukriky.size()) return 0;

    int typ_aktualneho = cukriky[pozicia_aktualneho];
    int chutnost_aktualneho = chutnost[typ_aktualneho];

    int zobrali_sme_aktualny = rek(pozicia_aktualneho+1, typ_aktualneho);
    int nezobrali_sme_aktualny = rek(pozicia_aktualneho+1, typ_predosleho);

    if (typ_predosleho == typ_aktualneho){
        return max(nezobrali_sme_aktualny, zobrali_sme_aktualny + chutnost_aktualneho);
    } else {
        return max(nezobrali_sme_aktualny, zobrali_sme_aktualny + cena_nova);
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    cukriky.resize(n);
    for (int i=0; i<n; i++) {
        cin >> cukriky[i];
        cukriky[i]--;
    }

    chutnost.resize(m);
    for (int i=0; i<m; i++) {
        cin >> chutnost[i];
    }

    cin >> cena_nova;

    // zavoláme sa na prvý cukrík, predchádzajúci zjedený je žiadny
    cout << rek(0, -1) << endl;
    return 0;
}

Dynamické programovanie

Poďme teda vymyslieť niečo rýchlejšie. Takéto rekurzívne riešenie totiž zbytočne veľakrát počíta stále tie isté hodnoty: Vezmime si postupnosť cukríkov 1 1 1 1. Už pri takto malom vstupe trikrát počítame hodnotu funkcie rek pre tretí cukrík, ak predchádzajúci bol typu \(1\) – raz pre možnosť, kedy zoberieme iba prvý cukrík, raz keď zoberieme iba druhý a raz keď zoberieme oba.

Hodnota, ktorú vráti funkcia rek(2, 1) (2 prislúcha tretiemu cukríku, lebo indexujeme od 0) sa však nezmení bez ohľadu na to, ktorú z týchto možností sme zvolili. Ak by sme sa dokázali vyhnúť tomu, aby sme počítali tú istú vec duplicitne, naše riešenie by sa určite zrýchlilo.

Pri rekurzívnych funkciách existuje spôsob ako niečo takéto docieliť – volá sa memoizácia. V podstate spočíva v tom, že po vypočítaní nejakej hodnoty si zapamätáme tento výsledok a nabudúce, keď náš program bude potrebovať spočítať túto hodnotu, iba si ju nájde v pamäti. Viac sa o memoizácii môžete dozvedieť napríklad v tomto vzorovom riešení: https://www.ksp.sk/ulohy/riesenia/1098/

Použitím memoizácie na vyššie ukázanú rekurziu by sme dostali riešenie s časovou zložitosťou \(O(nm)\), za ktoré by sme dostali 4 body. Toto riešenie však následne už nevieme zlepšiť, preto sa na náš problém musíme pozrieť z inej strany.

Pokúsme sa vyriešiť takúto úlohu: Akú najväčšiu chutnosť vie mať postupnosť končiaca cukríkom na \(i\)-tej pozícii? Túto najväčšiu možnú chutnosť si označme \(D[i]\).

Keďže vieme, ktorý cukrík zjeme ako posledný (\(i\)-ty), možno má zmysel pozrieť sa na to, ktorý sme zjedli ako predposledný. Ten totiž ovplyvní, ako nám bude chutiť ten na pozícii \(i\). Nech je predposledný zjedený cukrík na pozícii \(j\). Potom na základe toho, či sú \(i\)-ty a \(j\)-ty cukrík rovnakého typu vieme povedať, ako veľmi nám chutil ten na pozícii \(i\).

Všimnime si však, že \(i\)-ty cukrík, keďže je posledný, nám neovplyvní ako nám chutili predošlé cukríky v postupnosti. Preto ak chceme mať čo najväčšiu chutnosť a vieme, že na predposlednej pozícii je \(j\)-ty cukrík, najväčšia chutnosť postupnosti končiacej \(j\)-tym cukríkom je \(D[j]\).

Preto platí, že:

• Ak je \(i\)-ty cukrík rovnakého typu ako \(j\)-ty, najväčšia možná chutnosť postupnosti, ktorá končí týmito dvoma cukríkmi je \(D[i] = D[j] + chutnost[typ[i]]\)

• Ak sú dva posledné cukríky rôznych typov, chutnosť postupnosti je \(D[i] = D[j] + c\) (kde \(c\) je chutnosť cukríka ak nasleduje po cukríku iného typu)

My síce nevieme, ktorý cukrík bol predposledný, teda čo je tá pozícia \(j\), nič nám však nebráni, aby sme vyskúšali všetky možnosti medzi 0 až \(i-1\) a z nich si vybrali tú najlepšiu. Zapísané ako vzorec:

\[ rovnaky predosly = chutnost[typ[i]] + \max \lbrace D[j] ~|~ j \leftarrow 0, 2, \dots, i-1; typ[i] = typ[j] \rbrace\] \[ iny predosly = c +\max \lbrace D[j] ~|~ j \leftarrow 0, 2, \dots, i-1; typ[i] \neq typ[j] \rbrace\] \[D[i] = \max \lbrace rovnaky predosly, iny predosly\rbrace\]

Vyrobíme si teda pole D[], v ktorom budeme mať pre každý cukrík uloženú najväčšiu chutnosť postupnosti, akú vieme dosiahnuť, ak ho vezmeme ako posledný. Keďže pri výpočte hodnoty \(D[i]\) potrebujeme poznať všetky hodnoty \(D[j]\) pre \(j < i\), budeme hodnoty tohto poľa vypĺňať zaradom od prvej pozície. Takýto prístup, kde z menších hodnôt postupne počítame čím ďalej väčšie hodnoty, sa nazýva dynamické programovanie.

Keď vyplníme celé pole, tak výsledok bude maximálna hodnota v ňom, a tú vypíšeme.

Pre spočítanie jednej hodnoty \(D[i]\) sa potrebujeme pozrieť na predošlých \(i-1\) políčok. Celkovo sa preto pozrieme na \(0 + 1 + 2 + ... + (n-1) = \frac{(n-1)n}{2}\) políčok, a časová zložitosť tohto algoritmu bude \(O(n^2)\). Za takéto riešenie ste na testovacích vstupoch mohli získať \(3\) body.

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int n, m, c;
vector<int> cukriky;    
vector<int> chutnosti;

vector<long long> D; // D[pozicia posledneho] -> cena

int main(){
    scanf(" %d %d", &n, &m);
    cukriky.resize(n);
    chutnosti.resize(m);

    for(int i=0; i<n; i++){
        scanf(" %d", &cukriky[i]);
        cukriky[i]--;
    }

    for(int i=0; i<m; i++)
        scanf(" %d", &chutnosti[i]);
    
    scanf(" %d", &c);
    
    D.resize(n, 0LL);
    for(int i=0; i<n; i++){
        long long najlepsie = c;
        for(int j=0; j<i; j++)
            if (cukriky[i] == cukriky[j])
                najlepsie = max(najlepsie, D[j] + (long long)(chutnosti[cukriky[i]]));
            else
                najlepsie = max(najlepsie, D[j] + (long long)(c));
        D[i] = najlepsie;
    }

    long long maxi = 0;
    for(int i=0; i<n; i++)
        maxi = max(maxi, D[i]);
    printf("%Ld\n", maxi);
}

Jemné vylepšenie

V predchádzajúcom riešení si môžeme všimnúť, že pri počítaní \(D[i]\) prechádzame všetkých \(i-1\) políčok poľa \(D\) len preto, aby sme spomedzi nich vybrali buď najväčšie \(D[j]\), kde cukrík \(j\) má rovnaký typ ako cukrík \(i\) alebo najväčšie \(D[j]\) zo všetkých ostatných.

Predstavme si, že dva cukríky na pozícii \(a\) a \(b\) sú rovnakého typu a máme pre ne vypočítané hodnoty \(D[a]\) a \(D[b]\), pričom platí \(D[a] < D[b]\). Uvedomme si, že pri počítaní ďalších hodnôt \(D[i]\) sa budeme vždy pozerať na obe tieto pozície, budú patriť do tej istej skupiny (rovnaký alebo rôzny ako \(i\)-ty cukrík) a vždy z nich budeme vyberať maximum. Hodnotu \(D[a]\) teda už nikdy viac nebudeme potrebovať, lebo hodnota \(D[b]\) je proste lepšia.

Bude nám preto stačiť, ak si pre každý typ cukríka zapamätáme len tú najväčšiu hodnotu \(D[i]\), ktorú sme dovtedy videli ak \(i\)-ty cukrík bol príslušného typu.

Budeme mať teda pole T[] veľkosti \(m\), kde na \(k\)-tej pozícii bude uložená najväčšia doteraz videná chutnosť postupnosti, ktorá končí cukríkom typu \(k\). Hodnotu \(D[i]\) potom budeme počítať tak, že buď zoberiem hodnotu postupnosti končiacej rovnakým typom cukríka, teda hodnotu \(T[typ[i]]\) alebo maximum zo všetkých ostatných.

V našom programe dokonca vynechávame samotné pole D[], namiesto hodnoty D[i] používame iba lokálnu premennú najlepsie. Všimnite si tiež, že na záver nezabudneme hodnotu najlepsie vložiť do poľa T[typ[i]] – samozrejme, ak je väčšia ako doterajšia hodnota.

Takéto riešenie má zložitosť \(O(nm)\) a na testovacích vstupoch dostalo \(4\) body.

...

vector<long long> T; // T[typ] -> najlepsia cena

...

T.resize(m, -1LL);
for(int i=0; i<n; i++){
    long long najlepsie = c;
    for(int j=0; j<m; j++)
        if (T[j] == -1LL)
            najlepsie = max(najlepsie, (long long)(c));
        else if (cukriky[i] == j)
            najlepsie = max(najlepsie, T[j] + (long long)(chutnosti[j]));
        else
            najlepsie = max(najlepsie, T[j] + (long long)(c));
    T[cukriky[i]] = max(T[cukriky[i]], najlepsie);
}

...

Ešte o rád rýchlejšie

Označme si najväčšiu chutnosť spomedzi cukríkov iných typov než typu \(k = typ[i]\) ako: \[M_k = \max\lbrace T[1], T[2], \dots T[k-1], T[k+1], \dots T[m]\rbrace\]

Hodnotu \(D[i]\) sme teda v predošlom riešení počítali ako \(\max\lbrace T[k] + chutnost[k], M_k + c\rbrace\).

Strácali sme ale veľa času tým, že sme \(M_k\) vždy hľadali v čase \(O(m)\) – prezeraním všetkých ostatných typov. Takmer vždy nám ale stačí pamätať si len najväčšiu chutnosť zo všetkých, \(M = \max\lbrace T[1], T[2], \dots T[m]\rbrace\). Chutnosť postupnosti, ktorá končí \(i\)-tym cukríkom, ktorý má typ \(k\) vieme teda spočítať ako \(T[k] = \max\lbrace T[k] + chutnost[k], M + c\rbrace\).

Hodnota \(M\) však patrí niektorému typu cukríkov. A ak je \(i\)-ty cukrík rovnakého typu, tak neplatí, že \(M_{typ[i]} = M\) (\(M_{typ[i]}\) je maximum z typov iných ako \(typ[i]\)). V takomto prípade by sme museli spočítať hodnotu \(M_{typ[i]}\) a použiť tú.

V skutočnosti ju ale nemusíme počítať, stačí si zapamätať typ cukríka, ktorým končí druhá doteraz najchutnejšia postupnosť a použiť ju namiesto \(M_{typ[i]}\).

V našom riešení si teda budeme pamätať pole pre chutnosti jednotlivých typov, T[], a dva typy s najväčšími chutnosťami \(a\) a \(b\), pričom \(T[a] \geq T[b]\).

• Pri výpočte chutnosti postupnosti, ktorá končí \(i\)-tym cukríkom sa pozrieme na postupnosť, ktorá končila rovnakým typom, a jedna možnosť výsledku bude \(T[typ[i]] + chutnost[typ[i]]\).

• Druhá možnosť výsledku je taká, že zoberieme najchutnejšiu postupnosť, ktorá končí iným typom cukríka ako \(typ[i]\) a potom je možnosť výsledku \(M + c\), pričom \(M\) bude \(T[a]\) ak \(typ[i] \neq a\) a \(T[b]\) v opačnom prípade.

Z týchto dvoch možností vyberieme ako výsledok tú chutnejšiu.

Časová zložitosť riešenia je teda \(O(n)\), lebo pre každý cukrík overíme len pár podmienok a upravíme dva najvýhodnejšie typy.

n, m = [int(x) for x in input().split()]
cukriky = [int(x)-1 for x in input().split()]
chutnosti = [int(x) for x in input().split()]
c = int(input())

T = [-1] * m + [0]

najlepsi_typ = m
druhy_najlepsi_typ = m

for typ_i in cukriky:
    if typ_i != najlepsi_typ:
        M = T[najlepsi_typ]
    else:
        M = T[druhy_najlepsi_typ]
    
    if T[typ_i] == -1:
        T[typ_i] = M + c
    else:
        T[typ_i] = max(T[typ_i] + chutnosti[typ_i], M + c)

    if typ_i != najlepsi_typ:
        if T[typ_i] > T[najlepsi_typ]:
            druhy_najlepsi_typ = najlepsi_typ
            najlepsi_typ = typ_i
        elif T[typ_i] > T[druhy_najlepsi_typ]:
            druhy_najlepsi_typ = typ_i

print(max(*T))