Pentru a parcurge acest articol trebuie cunoscute următoarele: matrici și declararea variabilelor global, opțional și funcții.

#Cirese

Rezumat enunț: Se dă o livadă (sub forma unei matrici, iar fiecare număr din matrice reprezintă câte cirese pot fi strânse din pomul din acel punct) și apoi se citesc câte două perechi de coordonate pentru un număr de zone dreptunghiulare, coordonatele desemnând punctele din stânga sus și dreapta jos. Se cere să calculăm numărul maxim de cireșe care pot fi strânse din una din zonele date.

O primă idee este să folosim un algoritm de tipul brute force, care va calcula pur și simplu câte cireșe pot fi strânse de pe fiecare câmp (adunând pe rând fiecare element din acea zonă) și care apoi determină maximul.
În imaginea de mai sus este un exemplu. Programul va parcurge zona determinată de x1=3, x2=7, y1=3, y2=5 în ordinea indicată în imagine; zona ce trebuie analizată este colorată mai închis.
Implementarea programului este foarte simplă și obține, la această problemă, punctaj maxim.

Soluție:

#include <iostream>

using namespace std;

int n,m,nrzone,livada[101][101];

int main()
{
    cin>>n>>m>>nrzone;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            cin>>livada[i][j];
    int max=0;
    for(int p=1; p<=nrzone; p++)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;

        int s=0;

        for(int i=x1; i<=x2;i++)
            for(int j=y1;j<=y2;j++)
                s+=livada[i][j];

        if(s>max)
            max=s;
    }
    cout<<max;
    return 0;
}

Altă soluție, care folosește funcții:

#include <iostream>

using namespace std;

short int livada[101][101];

void citirematr(int n, int m)
{
    int i,j;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            cin<<livada[i][j];
}

int mere()
{
    int x1,y1,x2,y2,sum,i,j;
    cin>>x1>>y1>>x2>>y2;
    sum=0;
    for (i=x1;i<=x2;i++)
        for (j=y1;j<=y2;j++)
            sum+=livada[i][j];
    return sum;
}

int main()
{
    int n,m,nrzone,i,sum,max;
    cin>>n>>m>>nrzone;
    citirematr(n,m);
    max=0;
    for (i=0;i<nrzone;i++)
    {
        sum=mere();
        if (sum>max)
        max=sum;
    }
    cout<<max;
    return 0;
}

#Cirese1

Problema #Cirese1, așa cum evidențiază și autorul, este foarte asemănătoare cu #Cirese, singura diferență fiind că, în problema a doua, livada este mai mare și trebuie analizate mai multe zone. Totuși, limita de timp a crescut de la 0.1s la 0.8s.

Dacă se va copia codul de la problema anterioară fără nici o modificare, vom primi 20p, celelalte 80p (două teste de câte 40p) pierzându-se fiindcă livada depăsește limita de memorie. Dacă mărim dimensiunea matricei livada[][] așa încât noua livadă să încapă, vom primi 60p, ultimul test având limita de timp depășită. Prin urmare, algoritmul de natură brute force nu este suficient de eficient pentru a primi puncaj maxim la problema #Cirese1.

Ideea care va primi punctaj maxim nu este complicată, dar poate fi greu să o găsești. Algoritmul de 100p folosește o matrice suplimentară de sume parțiale. Odată formată această matrice, va fi foarte ușor să calculăm suma elementelor din orice zonă. Înainte de a continua, se cuvine să analizăm mai atent o asemenea matrice.

Caracteristicile generale ale matricei cu sume parțiale

Fiecare element din matricea cu sume parțiale va reprezenta suma tuturor elementelor din stânga și de deasupra elementului în cauză, inclusiv elementul respectiv. Spre exemplu, în imaginea de mai sus, pentru x=5 și y=4, corespondenta din matricea cu sume parțiale a căsuței analizate, colorată violet, va avea suma tuturor valorilor din căsuțele portocalii plus căsuța violet însăși. Cu alte cuvinte:
sume[5,4] = livada[1,1] + livada[1,2] + livada[1,3] + livada[1,4] + livada[2,1] +…+ livada[2,4] +…+ livada[5,1] +…+ livada[5,4]
Formula matematică de calcul este: \(\sum \limits_{k=1}^x (\sum \limits_{p=1}^y livada[k,p])\)

Calculul numărului de cireșe dintr-o zonă folosind matricea cu sume parțiale

Acum vom discuta despre cum putem calcula numărul de cireșe dintr-un câmp folosindu-ne doar de matricea cu sume parțiale (știu că încă nu am discutat cum putem construi eficient această matrice, vom analiza foarte curând și acest proces).

Așadar, vom presupune că am construit deja matricea cu sume parțiale, pe care am numit-o sume. Vrem să calculăm câte mere sunt pe câmpul avand coordonatele colțurilor din stânga sus, respectiv dreapta jos (x1,y1) și (x2,y2), spre exemplu (4,3) și (8,5).

Putem cuprinde merele din acea zonă dacă adunăm variabilei în care calculăm numărul de mere din câmpul descris mai sus elementul sume[x2,y2], adică sume[8,5]; am hașurat în poza de mai sus cu roșu câmpurile care intră în calcul la acest pas. Dar, dacă facem asta, vom avea calculate și merele din dreptunghiurile exact de deasupra, din stânga și din stânga-sus celui care ne interesează. Pentru a scăpa de ele, vom scădea mai departe sume[x1-1,y2] și sume[x2,y1-1], adică sume[3,5] și sume[8,2]. În imagine, câmpurile scăzute astfel sunt hașurate cu albastru, respectiv verde. Observăm acum că avem un dreptunghi care este adunat o dată și scăzut de două ori: dreptunghiul determinat de coordonatele (1,1) și (x1-1,y1-1), adică (3,2). Dacă adunăm sume[x1-1,y1-1], cu alte cuvinte sume[3,2] (spațiu hașurat cu violet), observăm că nu a mai rămas în calcul decât zona care ne interesa. Putem deci deduce acum o formulă de calcul:
\(Mere((x1,y1),(x2,y2))=sume[x2,y2]-sume[x2,y1-1]-sume[x1-1,y2]+sume[x1-1,y1-1]\)

Construirea matricei cu sume parțiale

Observăm că, in cazul particular în care x1=x2=x și y1=y2=y, nu mai este vorba de un câmp, ci de o singură căsuță. Înlocuind în relația de mai sus:
\(Mere(x,y)=sume[x,y]-sume[x,y-1]-sume[x-1,y]+sume[x-1,y-1]\)
De fapt, acum dorim să calculăm sume[x,y] cunoscând toate câmpurile matricei sume din stânga și de deasupra, dar și cunoscând numărul de mere din câmpul respectiv (adică livada[x,y]; cu alte cuvinte, Mere(x,y) este tot una cu livada[x,y]). Dacă izolăm în partea dreaptă a egalului termenul care ne interesează și apoi inversăm membrii obținem chiar formula de calcul pentru sume[x,y]:
\(sume[x,y]=sume[x,y-1]+sume[x-1,y]-sume[x-1,y-1]+livada[x,y]\)
Interpretarea grafică corespunzătoare formulei este asemănătoare cu cea de mai sus, schimbându-se doar semnele și ordinea.

Rezolvarea problemei

Având acum analiza completă a aceste matrici, putem discuta rezolvarea problemei. Primul pas va fi bineînțeles construcția matricei sume, proces descris mai sus; vom începe prin a pune în sume[1,1] valoarea din livada[1,1] (deoarece acea căsuță nu are altele deasupra și în stânga). Apoi completăm căsuțele de pe marginile din stânga și de sus, care nu au alte căsuțe în stânga, respecitv deasupra lor. Prin urmare, formulele de calcul pentru ele vor fi puțin diferite:

• \(sume[1,y]=sume[1,y-1]+livada[1,y];y=\overline{1,m}\)
• \(sume[x,1]=sume[x-1,1]+livada[x,1];x=\overline{1,n}\)

Celelalte elemente le vom calcula cu formula normală:
\(sume[x,y]=sume[x,y-1]+sume[x-1,y]-sume[x-1,y-1]+livada[x,y]\)
Apoi vom calcula numărul de mere de pe fiecare câmp citit de la tastatură folosind formula de mai sus, pe care o rescriu aici:
\(Mere(x,y)=sume[x,y]-sume[x,y-1]-sume[x-1,y]+sume[x-1,y-1]\)
Este important de precizat că elementele matricei sume le vom calcula pe rând, de sus în jos, de la stânga la dreapta.
Comparăm numărul obținut cu suma maximă (care inițial va fi 0) și suprascriem dacă găsim o valoare mai mare. La final, în urma analizei tuturor câmpurilor, afisăm valoarea maximă. Atașez mai jos soluțiile, dar doresc să accentuez că este foarte important să încerci să faci singur programul pentru a ține minte mai bine ideea!

#include <iostream>
using namespace std;

int n,m,k,livada[1001][1001];
int sume[1001][1001];

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


    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            cin >> livada[i][j];

    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
                sume[i][j] = livada[i][j] + sume[i-1][j] + sume[i][j-1] - sume[i-1][j-1];

    long long int Max = 0;
    for(int p = 1 ; p < k ; p ++)
    {
        int i1,j1,i2,j2;
        cin >> i1 >> j1 >> i2 >> j2;
        int SC = sume[i2][j2] - sume[i1-1][j2] - sume[i2][j1-1] + sume[i1-1][j1-1];
        if(SC > Max)
            Max = SC;
    }
    cout << Max << endl;
    return 0;
}

Soluția cu funcții:

#include <iostream>

using namespace std;

int livada[1005][1005],sume[1005][1005];

void citirematr(int n, int m)
{
    int i,j;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            cin>>livada[i][j];
}

void matraux(int n, int m)
{
    int i,j;
    sume[1][1]=livada[1][1];
    for (j=2;j<=m;j++)
        sume[1][j]=sume[1][j-1]+livada[1][j];
    for (i=2;i<=m;i++)
        sume[i][1]=sume[i-1][1]+livada[i][1];
    for (i=2;i<=n;i++)
        for (j=2;j<=m;j++)
        sume[i][j]=sume[i-1][j]+sume[i][j-1]-sume[i-1][j-1]+livada[i][j];
}
int cirese()
{
    int x1,y1,x2,y2;
    long long int x;
    cin>>x1>>y1>>x2>>y2;
    x=sume[x2][y2]-sume[x1-1][y2]-sume[x2][y1-1]+sume[x1-1][y1-1];
    return x;
}

int main()
{
    int n,m,k,i,smax;
    long long int x;
    cin>>n>>m>>k;
    citirematr(n,m);
    matraux(n,m);
    smax=0;
    for (i=0;i<k;i++)
    {
        x=cirese();
        if (x>smax)
            smax=x;
    }
    cout<<smax;
    return 0;
}