Probleme de informatica - enunturi si rezolvari

Probleme de informatică
Clasa a IX-a
Elementele de bază C++ (46)
Subprograme predefinite (1)
Fişiere text (2)
Algoritmi elementari (109)
Tablouri unidimensionale (83)
Tablouri bidimensionale (64)
Probleme diverse (13)
Clasa a X-a
Subprograme (funcții) (87)
Şiruri de caractere (49)
Tipul înregistrare (26)
Recursivitate (57)
Alocarea dinamică a memoriei (2)
Liste înlănţuite (25)
Algoritmul lui Lee (1)
Clasa a XI-a
Metoda "Divide et impera" (12)
Metoda Backtracking (85)
Metoda Greedy (6)
Programare dinamică (18)
Grafuri neorientate (37)
Grafuri orientate (38)
Arbori (33)
Clasa a XII-a
Elemente de bază C# (32)
POO în C# (13)
Programare vizuală în C# (10)
Examen de bacalaureat
Competențe digitale
Examen de atestat
Admitere UBB (18)
Cladirea Finantelor publice este formata din birouri dispuse intr-un dreptunghi cu nXm elemente. Intre doua birouri se poate trece daca sunt alaturate pe linie sau pe coloana.
Pentru fiecare birou se cunoaste valoare taxei care trebuie platita in acel birou (valoare naturala). Un contribuabil intra in cladire prin biroul 1,1 si trebuie sa o parareasca prin biroul n,m. Calculati suma minima a taxelor pe care le poate plati contribuabilul de la intrare pana la iesirea din cladire.
Exemplu:
n=4, m=3, dispunerea birourilor si taxa din fiecare:
3 7 2
6 4 3
6 3 1
6 2 2
Valoarea minima pe care o poate plati contribuabilul este 18 (corespunde parcurgerii birourilor cu taxele: 3 7 2 3 1 2)

#include<fstream>
using namespace std;
ifstream fin ("date.in");
ofstream fout ("date.out");

int main()
{
    int a[100][100],s[100][100]={0};
    int i,j,m,n;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            fin>>a[i][j];
            if(i==1 && j==1) s[i][j]=a[i][j];
            else if(i==1) s[i][j]=s[i][j-1]+a[i][j];
                 else if(j==1) s[i][j]=s[i-1][j]+a[i][j];
                      else if(s[i-1][j]<s[i][j-1]) s[i][j]=s[i-1][j]+a[i][j];
                           else s[i][j]=s[i][j-1]+a[i][j];
        }

    fout<<s[n][m]<<endl;
    fin.close();
    fout.close();
    return 0;
}

17 aug 2018
Site-ul conține 867 de probleme rezolvate
Copyright © 2009-2018 Muresan Vasile Ciprian