Cerinţa

Ali Baba și cei 40 de hoți stăpânesc un deșert de formă dreptunghiulară, împărțit în n linii și m coloane, care definesc n*m sectoare. În fiecare sector se află o comoară ascunsă de Ali Baba. Se cunoaște valoarea în galbeni a fiecărei comori.

Un călător trebuie să traverseze deșertul de la Nord la Sud, trecând dintr-un sector în altul, astfel: din sectorul (i j) se poate ajunge în unul din sectoarele (i+1,j-1), (i+1,j) sau (i+1,j+1), dar fără a părăsi deșertul (ar fi omorât de oamenii lui Ali Baba). La trecerea printr-un sector, călătorul colectează comoara din acel sector.

Determinați valoarea totală maximă a comorilor pe care le poate colecta călătorul la traversarea deșertului, știind că pleacă din orice sector al liniei 1 (Nord) și se oprește în orice sector al linei n (Sud), cu respectarea condițiilor de mai sus.

Date de intrare

Fişierul de intrare comori.in conţine pe prima linie numerele n m. Următoarele n linii conțin câte m numere naturale, reprezentând valorile comorilor din fiecare sector.

Date de ieşire

Fişierul de ieşire comori.out va conţine pe prima linie numărul V, reprezentând valoarea maximă a comorilor care pot fi colectate.

Restricţii şi precizări

1 ≤ n,m ≤ 200
valoarea fiecărei comori este un număr natural mai mic decât 100

Exemplu

comori.in

comori.out

Explicație

Un traseu prin care se colectează comori în valoare de 29 galbeni este:

5	8	3	7	7
1	1	4	5	1
5	8	9	1	7
5	8	6	6	9

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Comori:

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
using namespace std;
#define NN 205

ifstream fin("comori.in");
ofstream fout("comori.out");

int n, m, a[NN][NN], s[NN][NN];

int Maxim(int x , int y){
    return x>y ? x : y;
}

int Maxim(int x, int y, int z)
{
    return Maxim(Maxim(x , y) , z);
}

int Maxim(int * v, int * u)
{
    int M = *v;
    for( v++; v!=u; v++)
        M = Maxim(M,*v);
    return M;
}

int main(){
    assert(fin >> n >> m);
    for(int i=1 ; i<=n ; ++i)
        for(int j=1 ; j<=m ; j++)
            assert(fin >> a[i][j]);
    for(int j=1;j<=m;++j)
        s[1][j] = a[1][j];
    
    for(int i=2; i<=n;++i){
        s[i][1] = a[i][1] + Maxim(s[i-1][1], s[i-1][2]);
        
        s[i][m] = a[i][m] + Maxim(s[i-1][m-1],s[i-1][m]);
        for(int j=2 ; j<m ; ++j)
            s[i][j] = a[i][j] + Maxim(s[i-1][j-1] , s[i-1][j] , s[i-1][j+1]);
    }
    fout << Maxim(s[n]+1, s[n]+m+1) ;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #395 Comori

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #395 Comori de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #395 Comori