p14-veverita

/*

O padure este impartita in nXm zone. In fiecare zona creste cate un pom. Din fiecare pom cade pe jos o cantitate de ghinde.
In zona stanga sus se afla un veverita care vrea sa ajunga in zona dreapta jos. veveritaul se poate deplasa doar pe doua directii: in jos sau spre dreapta.
Determinati cantitatea maxima de ghinde pe care le poate aduna veveritaul prin deplasarea din pozitia initiala in cea dorita.
Citirea se face din fisierul veverita.in care contine pe prima linie dimensiunile livezii, adica n si m, si apoi cantitatea de ghinde din fiecare dintre cele nXm zone.
Afisarea cantitatii maxime de ghinde se va face in fisierul veverita.out.
Exemplu:
veverita.in
3 3
0 4 1
0 1 1
1 0 1
veverita.out
7

http://info.mcip.ro/?cap=Programare%20dinamica&prob=750
*/


#include<fstream>
using namespace std;
ifstream f("p14-veverita.in");
ofstream g("p14-veverita.out");

int a[101][101]; // a[i][j] = va retine cantitatea de ghinde.
int c[101][101]; // c[i][j] = cantitatea maxima (castigul) ce se poate obtine ajungand in pozitia i,j;
                 // c[i][j] = a[i][j] + max(c[i-1][j],c[i][j-1]);
                 // adica nr de ghinde din pozitia curenta + (castigul obtinut daca se coboara in jos (c[i-1][j]) sau castigul obtinut daca se muta la dreapta  (c[i][j-1]))
int n,m,i,j;

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

int main() {
    // citim datele din fisier
    f>>n>>m;
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++) {
            f>>a[i][j];
        }
    }

    //calculam matricea castigurilor
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++) {
            c[i][j] = a[i][j] + max(c[i-1][j],c[i][j-1]);
        }
    }
    g<<c[n][m];
    f.close();
    g.close();
    return 0;
}