Skúsenejšiemu riešiteľovi by mohlo rýchlo napadnúť riešiť túto úlohu dynamickým programovaním, čo sa ukáže ako dobrý nápad. Veľa úloh, ktoré má otázku “koľko najviac/najmenej” často býva riešených dynamickým programovaním.

Nad úlohou sa budeme ďalej zamýšľať spôsobom, že poznáme minimálnu cenu, za ktorú vieme dostať nejaký prefix postupnosti do požadovaného stavu. Potom budeme počítať prefix dĺžky o $1$ viac.

Teda ďalej v riešení uvažujeme, že už sme upravili do požadovaného tvaru postupnosť dĺžky $i$ a zistili najnižšiu cenu za ktorú to dokážeme spraviť. Potom vypočítame odpoveď pre postupnosť, ktorá s vypočítanou postupnosťou má zhodné prvky až po $i$, ale má jeden ďalší prvok $i + 1$.

Stavy dynamického

programovania

V tomto riešení budem používať značenie $minc$, aby som zaznačil minimálnu cenu, za ktorú vieme dostať niečo do stavu, ktorého chceme.

Všimnime si, že aby sme zistili $minc$ pre o $1$ väčší prefix nás nemusia zaujímať presné úpravy, ktoré sme spravili a ani celý upravený prefix. Zaujímavý je len posledný prvok v upravenom prefixe. Ak chceme rozšíriť prefix upravený do vyhovujúceho tvaru, tak jediné čo potrebujeme zabezpečiť je, aby jeho posledný prvok a novo pridaný prvok mali rozdiel $\leq M$.

Tiež je dobré si uvedomiť, že posledný prvok v upravenom prefixe nemá zmysel nikdy uvažovať väčší, ako $max A_i$, keďže potom by sme ho mohli nahradiť $max A_i$ a dostali by sme takú istú, alebo nižšiu cenu.

Z toho už vyplýva, že budeme chcieť vypočítať hodnoty $dp[i][k]$ - najmenšia cena, pomocou ktorej vieme upraviť prefix veľkosti $i$ do požadovaného tvaru tak, že sa bude končiť na prvok $k$. Finálna odpoveď potom bude najmenšia hodnota poľa $dp[n]$, kde $n$ je dĺžka danej postupnosti.

Ešte si ale môžeme všimnúť, že v optimálnom riešení bude posledný prvok upravenej postupnosti do požadovaného tvaru stále nejaký prvok pôvodnej postupnosti. Ak by to bol vkladaný prvok, tak ho vieme nevložiť a dostať lepšiu cenu za trochu inú, ale tiež vyhovujúcu postupnosť. Toto vieme využiť a trochu upraviť, čo reprezentuje $dp[i][k]$. Pridáme podmienku, že prvok $k$ musí byť upravený prvok pôvodnej postupnosti. S touto podmienkou stále dostaneme správnu odpoveď, ale pomôže nám to neskôr pri vymýšľaní prechodov medzi stavmi.

Riešenie na 6b

Teraz chceme vymyslieť spôsob, ako pomocou hodnôt zapamätaných pre nejaký prefix vypočítať nové hodnoty pre o $1$ väčší prefix.

Stále je možnosť zmazať novo pridaný prvok za cenu $D$. Teda môžeme použiť operácie na najlacnejšiu úpravu prvých $i$ prvkov do požadovaného tvaru a novo pridaný prvok zmažeme. Cenu na začiatku tak môžeme nastaviť $dp[i + 1][k] = dp[i][k] + D$ pre každé $k$ a získať minimálne ceny pre každé $k$, ak použijeme operáciu zmazania.

Teraz ešte ostáva zistiť $minc$, ak novo pridaný prvok nemažeme. Uvažujme teda, že chceme vypočítať $dp[i + 1][k]$ pre nejaké konkrétne $k$. Keďže vieme, že nový prvok nemažeme a tiež sme si dali podmienku, že posledný prvok musí byť z pôvodnej postupnosti, musíme zaplatiť $|A_{i + 1} - k|$ za operáciu zmeny prvku. Ešte ostáva zistiť, na akú upravenú postupnosť je najvýhodnejšie nadviazať. Teda aký prvok chceme mať na poslednom mieste v predchádzajúcom prefixe. Uvažujme, že je to $l$. Môžeme si všimnúť, že v takomto prípade už je presne dané, čo musíme robiť - vložiť medzi posledné $2$ čísla čo najmenej prvkov tak, aby nemali žiadne rozdiel väčší ako $M$. To sa dá už ľahko vypočítať - budeme vkladať prvky tak, aby boli vo vzdialenosti presne $M$ od seba, pokým nebude posledný dostatočne blízko $k$. Označme túto dopočítanú cenu $x$. Teda ak nadväzujeme na prefix dĺžky $i$, ktorý sa po úprave končí na $l$, najnižšia cena, ktorú vieme dostať bude $dp[i][l] + |A_{i + 1} - k| + x$.

Teraz už nie je ťažké vymyslieť, ako to bude celé fungovať. Postupne pre každý prefix veľkosti $i$ pre $i$ od $1$ do $n$ pre všetky možné $k$ vyskúšať všetky možné $l$ a podľa popísaného postupu stále dopočítať $dp[i][k]$. Dostaneme tak funkčný algoritmus, pomocou ktorého vieme získať odpoveď ako minimum z hodnôt $dp[n]$. Tento algoritmus bude mať časovú zložitosť $O(n \cdot (max A_i)^2)$, keďže pre každý prefix prejdeme všetky možné dvojice $(l, k)$. Toto stačilo na program za $6$ bodov.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M, I, D;
    cin >> N >> M >> I >> D;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    int K = *max_element(a.begin(), a.end());

    vector<int> dp(K + 1, 0);
    for (int i = 0; i < N; i++) {
        vector<int> new_dp(K + 1, 0);
        for (int j = 0; j <= K; j++) {
            new_dp[j] = dp[j] + D;
        }
        for (int from = 0; from <= K; from++) {
            for (int to = 0; to <= K; to++) {
                int old_to = to;
                if (M == 0) to = from;

                int diff = max(0, abs(from - to) - M);
                int inserts_cost = (M == 0) ? diff : I * ((diff + M - 1) / M);
                int move_cost = abs(a[i] - to);
                int cost = dp[from] + inserts_cost + move_cost;
                new_dp[to] = min(new_dp[to], cost);

                to = old_to;
            }
        }
        dp = new_dp;
    }
    int res = *min_element(dp.begin(), dp.end());
    cout << res << endl;
}

Optimálne riešenie

Vypočítať hodnotu $dp[i + 1][k]$ rovno na základe $dp[i]$ v konštantnom čase sa javí ako pomerne ťažká úloha. Skúsme preto nejak efektívne vypočítať medzistav, z ktorého už bude ľahšie získavať odpovede pre $dp[i + 1][k]$. Označme tento medzistav $dp_2[i][k]$. Bude nám hovoriť, koľko najmenej musíme zaplatiť, aby sme skončili na prvku $k$ a mali vyhovujúcu postupnosť, ale nemusíme končiť už na prvku pôvodnej postupnosti. Teda je povolené vkladať prvky aj za posledný prvok z pôvodnej postupnosti.

Pozrime sa na vkladanie prvkov pri popísanom algoritme za 6 bodov. Ak sme končili na prvku $l$, tak sme vkladali buď postupne prvky $l + M, l + 2M, …$ až pokým sme sa nedostali dostatočne blízko ku $k$, alebo $l - M, l - 2M, …$, až pokým sme sa nedostali dostatočne blízko ku $k$. Ak by sme teda dostali optimálnu odpoveď pre nejaké $dp_2[i][k]$ vkladaním prvkov menších ako $k$, tak na jej výpočet nebudeme potrebovať vedieť odpoveď pre $dp_2[i][l]$ také, že sme sa k nej dostali vkladaním prvkov väčších ako $l$. Ak by sme tieto hodnoty potrebovali, znamenalo by to, že je niekedy optimálne vložiť prvky $…, l + M, l, …, k - M, k$. Vidíme, že v tomto prípade je zbytočné vložiť prvok s hodnotou $l$, alebo prvok $l + M$ (podľa toho, či $l < k$, alebo $l > k$) a teda to nemôže byť optimálna odpoveď.

Z toho vyplýva, že môžeme najprv napríklad vypočítať $dp_2[i][k]$ pre prípad, že budeme vkladať prvky menšie ako $k$ (($…, k - 2M, k - M$). Toto by sme chceli vypočítať pre všetky $k$ v čase $O(max A_i)$. Spravíme to prechodom od najmenších hodnôt po najväčšie s tým, že si budeme pamätať stále najlepší posledný prvok, od ktorého budeme chcieť vkladať hodnoty vo vzdialenosti $M$ od seba tak, že sa dostaneme dostatočne blízko k aktuálne počítanému prvku $k$. Najlepší posledný prvok si vieme jednoducho udržiavať, keďže pri tomto prechode bude stále len stúpať. Ak sme aktuálne na indexe $k$ vieme povedať, že bude určite lepší pre všetky $q \geq k$, ako aktuálne najlepší index $p$ ak: $dp[i][k] < I \cdot (\lfloor(k - p) / M \rfloor) + dp[i][p]$. Hodnotu $dp_2[i][k]$ teda vieme vypočítať ako $min(dp[i][k], I \cdot (\lfloor(k - p) / M \rfloor) + dp[i][p])$, kde $p$ je najlepší posledný prvok. Následne spravíme to isté ale opačne. Teda vypočítame ceny, ak vkladáme prvky väčšie ako $k$ ($…, k + 2M, k + M$). Teraz už samozrejme budeme zapisovať novú hodnotu, iba vtedy ak je menšia ako tá, ktorú sme vypočítali predchádzajúcim prechodom.

Keď už teraz máme vypočítané hodnoty po všetkých vkladaniach chceme zistiť, aké budú hodnoty $dp[i+1][k]$. Ako v algoritme za $6$ bodov, môžeme nastaviť $dp[i+1][k] = dp[i][k] + D$ pre prípad, že novo pridaný prvok zmažeme. Ak prvok nemažeme tak za $dp[i+1][k]$ zaplatíme $min_{j \in { k - M, …, k + M } }( dp_2[i][j] + |A_{i + 1} - k|)$. Zjavne uvažovať ostatné $j$ nemôžeme, keďže potom by rozdiel posledných prvkov bol väčší ako $M$. Ostáva už len domyslieť ako postupne efektívne počítať minimá zo súvislých úsekov dĺžky $2M + 1$. Toto je pomerne štandardná úloha a dá sa riešiť pomocou minimovej deque dokonca amortizovane v lineárnom čase. V našom prípade teda v $O(max A_i)$ na vypočítanie $dp[i+1][k]$ pre všetky $k$. Ako presne sa to dá spraviť sa môžete dočítať napríklad tu

Vymysleli sme algoritmus, ktorý vypočíta hodnoty $dp$ v $O(n \cdot max A_i)$, keďže hodnoty $dp_2[i]$ aj potom hodnoty $dp[i+1]$ počítame v $O(max A_i)$ pre $i$ od $1$ po $n$. Pamäťovú zložitosť vieme zlepšiť na $O(n + max A_i)$, keďže si pri počítaní $dp[i+1]$ si stačí pamätať hodnoty $dp[i]$. Teda nemusíme vytvárať celé dvojrozmerné pole, ale pamätať si stále iba jeho posledné $2$ “riadky”.

#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main() {
    int D, I, M, N;
    cin >> N >> M >> I >> D;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    int K = *max_element(a.begin(), a.end());

    vector<int> dp(K + 1, 0);
    for (int i = 0; i < N; i++) {
        vector<int> inter_dp(dp.begin(), dp.end());
        for (int k = 0; k < M; k++) {
            int best = -1;
            for (int j = k; j <= K; j += M) {
                if (best == -1 || I * ((j - best) / M) + dp[best] > dp[j]) {
                    best = j;
                }
                inter_dp[j] = min(inter_dp[j], I * ((j - best) / M) + dp[best]);
            }
        }
        for (int k = 0; k < M; k++) {
            int best = -1;
            for (int j = K - k; j >= 0; j -= M) {
                if (best == -1 || I * ((best - j) / M) + dp[best] > dp[j]) {
                    best = j;
                }
                inter_dp[j] = min(inter_dp[j], I * ((best - j) / M) + dp[best]);
            }
        }

        deque<int> q;
        for (int j = 0; j < min(K + 1, M); j++) {
            while (!q.empty() && inter_dp[q.back()] >= inter_dp[j]) {
                q.pop_back();
            }
            q.push_back(j);
        }
        vector<int> new_dp(K + 1, 0);
        for (int j = 0; j <= K; j++) {
            new_dp[j] = dp[j] + D;
        }
        for (int j = 0; j <= K; j++) {
            int last = j + M;
            if (!q.empty() && q.front() + M < j) {
                q.pop_front();
            }
            if (last <= K) {
                while (!q.empty() && inter_dp[q.back()] >= inter_dp[last]) {
                    q.pop_back();
                }
                q.push_back(last);
            }
            new_dp[j] = min(new_dp[j], inter_dp[q.front()] + abs(a[i] - j));
        }
        dp = new_dp;
    }
    int res = *min_element(dp.begin(), dp.end());
    cout << res << endl;
}