Zadanie

Kuko má rád sladkosti. Nepohrdne čokoládou, horalkou, ba ani čistým cukrom. No zo všetkého najradšej má rád cukríky. Takmer vždy má pri sebe otvorené vrecúško jeho obľúbených maškŕt.

Jedného krásneho dňa šiel ako každý správny matfyzák na prednášku. A ako každý správny vedúci samozrejme na poslednú chvíľu. No ako obiehal Zergbota s kofolou, potkol sa a celé balenie sa mu rozsypalo po chodbe.

Rád by ich čo najviac pozbieral späť do sáčku, no nemôže sa veľmi zdržať, keďže už aj tak mešká na prednášku. Preto vás požiadal o pomoc.

Úloha

Chodbu na matfyze si môžete predstaviť ako obdĺžnik \(n\times m\) dláždený štvorcovými kachličkami. Keď Kuko prejde cez kachličku, zoberie všetky cukríky, ktoré sú na nej vysypané. Začína v ľavom hornom rohu chodby, prednášku má v pravom dolnom. Keďže sa na ňu ponáhľa, tak sa k nej chce v každom kroku posunúť bližšie. Môže teda chodiť iba doprava alebo dole.

Vašou úlohou je zistiť, koľko najviac cukríkov vie Kuko vyzbierať a ako sa má hýbať aby sa mu to podarilo.

Úloha sa testuje na piatich sadách vstupov. Pre vyriešenie prvých \(2\) sád nemusíte vypisovať Kukovu cestu, stačí zistiť počet cukríkov. Za takýto program dostanete \(2\) body.

Pre jednotlivé testovacie sady platia nasledovné obmedzenia:

Sada Limity vstupov Treba cestu
\(1\) \(n,m \leq 10\) Nie
\(2\) \(n,m \leq 1\,000\) Nie
\(3\) \(n,m \leq 10\) Áno
\(4\) \(n,m \leq 100\) Áno
\(5\) \(n,m \leq 1\,000\) Áno

Formát vstupu

Na prvom riadku vstupu dostanete čísla \(n\) a \(m\) – rozmery chodby. Nasleduje \(n\) riadkov, každý obsahuje \(m\) čísel oddelených medzerou – počty cukríkov na jednotlivých kachličkách. Tieto čísla sú v rozsahu od \(1\) po \(10^6\).

Formát výstupu

Na prvý riadok vypíšte najväčší počet cukríkov, ktoré vie Kuko zozbierať. Na nasledulúci riadok vypíšte jeden reťazec bez medzier, reprezentujúci Kukovu trasu. Písmeno D označuje pohyb dole, písmeno R pohyb doprava. Ak existuje viacej optimálnych trás, vypíšte ľubovoľnú z nich.

Príklad

Input:

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

Output:

19
DRDRRDR

Pozrime sa najprv na trochu jednoduchšiu úlohu, v ktorej nebudeme musieť vypisovať celú Kukovu cestu, ale len počet cukríkov, ktoré nazbieral.

Rekurzia

Asi najjednoduchšie funkčné riešenie, aké sa dalo vymyslieť, je rekurzia.

Cheme zistiť, koľko najviac cukríkov mohol Kuko zobrať po ceste z ľavého horného rohu do pravého dolného rohu mapy. Dostať sa na pravé dolné políčko mohol buď zhora alebo zľava. Rekurzívne si zistíme, koľko najviac cukríkov vedel zozbierať na ceste zo začiatku do jedného z týchto políčok (túto otázku sa pýtam dvakrát, postupne pre obe políčka) a vyberieme si lepšiu možnosť. Tieto kratšie cesty vyrátame rovnakým spôsobom, buď sa na posledné políčko na nej prišiel zľava alebo zhora. Jedinou výnimkou sú políčka na ľavom a hornom okraji mapy, kde mám vždy len jednu možnosť, ako som sa mohol na ne dostať a ľavé horné políčko, kde nie je ani jedna možnosť.

Aká je časová zložitosť? Prvé volanie funkcie sa zavolá dvakrát, každé z týchto volaní sa však tiež zavolá dvakrát, čo je dokopy už štyrikrát, a čo nevidieť tu máme exponenciálnu časovú zložitosť. To nám zbehne tak na vstupoch do veľkosti \(10\), ale na ostatné potrebujeme niečo rýchlejšie.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

vector<vector<int>> mapa;

int zrataj(int x, int y){
	if (x<0 || y<0) return 0; //ak sme mimo mapy, vratime nulu
	
	int vlavo = zrataj(x, y-1); //vzdy sa rekurzivne zavolame na predchadzajuce policka
	int hore = zrataj(x-1, y);
	
	return mapa[x][y] + max(vlavo, hore); //vratime hodnotu pre toto policko
}

int main(){
	int n, m;
	cin>>n>>m;
	mapa.resize(n, vector<int> (m)); //nastavime velkost pola a nacitame mapu
	for (int i=0; i<n; i++){
		for (int j=0; j<m; j++){
			cin>>mapa[i][j];
		}
	}
	int vysledok = zrataj(n-1, m-1); //spytame sa na policko, ktore nas zaujima
	cout<<vysledok<<endl;
}

Rekurzia s memoizáciou

Riešenie obyčajnou rekurziou je pomalé preto, lebo veľakrát hľadáme cestu na to isté políčko. Algoritmus preto upravíme: namiesto toho, aby sme vždy danú cestu počítali nanovo, si ju spočítame len raz, výsledok uložíme do pamäte a pri ďalších otázkach vrátime rovno túto už vypočítanú hodnotu.

Vďaka tomu, že cestu na každé políčko prepočítavame najviac raz a pýtame sa ňu najviac dvakrát1, sa časová zložitosť rekurzie zlepšila na počet políčok, teda O(\(nm\)). Táto zložitosť je naviac najlepšia možná, lebo musíme načítať hodnotu všetkých políčok, čo nám zaberie čas \(O(nm)\).

Vypisovanie cesty

Vypisovanie cesty je pri vyššie uvedených algoritmoch už len čerešničkou na torte a dá sa doprogramovať veľmi jednoducho. Pri všetkých sme sa totiž pre danú cestu na políčko pýtali, či je lepšie ísť doňho zvrchu alebo zľava. Zapamätáme si teda, ktorá z týchto možností bola výhodnejšia, napríklad do dvojrozmerného poľa znakov. Z neho budeme na konci vedieť priamo vyskladať cestu – stačí, ak pôjdeme odzadu.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

vector<vector<int>> mapa;
vector<vector<int>> memo;
vector<vector<char>>path;

int zrataj(int x, int y){
    if (x<0 || y<0) return 0; //ak sme mimo mapy, vratime nulu
    
    if (memo[x][y] == -1) {	//ak sme si toto policko nevyratali, tak ideme na to
        int vlavo = zrataj(x, y-1);	
        int hore = zrataj(x-1, y);

        memo[x][y] =  mapa[x][y] + max(vlavo, hore); //zapiseme vysledok pre policko
        
        if(vlavo > hore){ //zapiseme si odkial sa oplatilo prist, aby sme vedeli spravit cestu
            path[x][y] = 'R';
        } else {
            path[x][y] = 'D';
        }
    }
    
    return memo[x][y]; //vratime vysledok pre policko, ci sme ho zratali teraz alebo uz kedysi predtym
}

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

    mapa.resize(n, vector<int> (m)); //nacitame mapu a poinicializujeme polia
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
                cin>>mapa[i][j];

    memo.resize(n, vector<int> (m, -1));
    path.resize(n, vector<char> (m));

    zrataj(n-1, m-1);

    cout<<memo[n-1][m-1]<<endl; //vypiseme posledne policko, na ktorom je odpoved

    string cesta;

    int i = n-1;
    int j = m-1;
    while(i != 0 || j != 0){ //vyskladame cestu od konca
        cesta += path[i][j];
        if (path[i][j] == 'R')
            j--;
        else
            i--;
    }

    reverse(cesta.begin(), cesta.end()); //cestu sme vyskladali od konca, tak ju prevratime
    cout<<cesta<<endl;
}

Dynamické programovanie

Táto úloha sa dala riešiť aj principiálne inak, než rekurziou, a to pomocou dynamického programovania. Pri rekurzii sme sa snažili zrátať rovno výsledok a postupne si dopočítavať zvyšné informácie, ako sme ich potrebovali. Dynamické programovanie sa na problém pozerá z opačného konca – z údajov, ktoré už poznáme vyráta ďalšie, až kým sa nedopracuje k výsledku. Postupne preto ráta najväčší počet cukríkov, ktoré vieme zozbierať na ceste na dané políčko, ale začína rátať v ľavom hornom rohu a od neho ide postupne doprava a dole.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

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

    vector<vector<int>> mapa;
    vector<vector<int>> memo;
    vector<vector<char>>path;

    mapa.resize(n, vector<int> (m)); //nacitame mapu a poinicializujeme polia (rovnako ako v rekurzii)
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            cin>>mapa[i][j];

    memo.resize(n, vector<int> (m, -1));
    path.resize(n, vector<char> (m));

    //zacneme ratat

    for(int i=0; i<n; i++){ //prejdeme postupne od laveho horneho rohu po riadkoch
            for(int j=0; j<m; j++){
                    int vlavo, hore;
                    vlavo = hore = 0;
                    if (i != 0) hore = memo[i-1][j]; //kontrolujeme, či nie sme na okraji mapy
                    if (j != 0) vlavo = memo[i][j-1]; //kedze ideme po mape postupne
                    // tak vieme ze policka vlavo a hore mame uz zratane

                    memo[i][j] = mapa[i][j] + max(vlavo, hore);
                    
                    if(vlavo > hore){
                            path[i][j] = 'R';
                    } else {
                            path[i][j] = 'D';
                    }
            }
    }
    
    string cesta;

    int i = n-1;
    int j = m-1;
    while(i != 0 || j != 0){ //vyskladame cestu od konca, rovnako ako pri rekurzii
            cesta += path[i][j];
            if (path[i][j] == 'R')
                    j--;
            else
                    i--;
    }

    reverse(cesta.begin(), cesta.end());
    cout<<cesta<<endl;
}

  1. raz keď počítame cestu na políčko pod ním a raz na cestu na políčko vpravo

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.