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. Intrarea într-un sector se plătește cu o taxă cunoscută, exprimată în galbeni.

Un călător trebuie să traverseze deșertul de la Est la Vest, trecând dintr-un sector în altul, astfel: din sectorul (i j) se poate ajunge în unul din sectoarele (i-1,j-1), (i,j-1) 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 plătește taxa aferentă acelui sector.

Determinați suma totală minimă pe care trebuie să o plătească călătorul la traversarea deșertului, știind că pleacă din orice sector al coloanei m (Est) și se oprește în orice sector al coloanei 1 (Vest), cu respectarea condițiilor de mai sus.

Date de intrare

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

Date de ieşire

Fişierul de ieşire taxe.out va conţine pe prima linie numărul S, reprezentând suma minimă care trebuie plătită.

Restricţii şi precizări

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

Exemplu

taxe.in

taxe.out

Explicație

Un traseu în care se plătesc 8 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 Taxe:

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

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

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

int Minim(int x , int y){
    return x<y ? x : y;
}

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

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 i=1;i<=n;++i)
        s[i][m] = a[i][m];
    for(int j = 1 ; j <= m ; ++j)
        s[0][j] = s[n+1][j] = INFINIT;
    for(int j=m-1 ; j>=1 ; j--)
        for(int i = 1 ; i <= n ; ++i)
            s[i][j] = a[i][j] + Minim(s[i-1][j+1], s[i][j+1], s[i+1][j+1]);
    int pmin  = 1;
    for(int i = 2 ; i <= n ; ++i)
        if(s[i][1] < s[pmin][1])
            pmin = i;
        
    fout << s[pmin][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 #432 Taxe

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #432 Taxe 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 #432 Taxe