Se dau L şi C două numere naturale şi o matrice cu L linii şi C coloane având elementele numere întregi. Trebuie alese elemente care să respecte următoarele proprietăţi:

de pe fiecare linie se alege o secvenţă de elemente aflate pe coloane cu indici consecutivi, începând cu elementul de pe prima coloană;
pentru orice două linii consecutive, lungimile secvenţelor alese trebuie să difere prin 1 sau să fie egale;
nu trebuie să existe 3 linii consecutive pentru care lungimile secvenţelor alese să fie egale, sau să fie în ordine strict crescătoare sau strict descrescătoare;

Cerința

Se cere să se facă o alegere a secvenţelor de pe fiecare linie a matricei respectând restricţiile precizate, astfel încât însumând elementele acestora să se obţină suma maximă posibilă.

Date de intrare

Prima linie a fişierului left.in conţine două numere naturale sunt L şi C separate printr-un spaţiu reprezentând în ordine numărul de linii şi numărul de coloane ale matricei date. Pe fiecare dintre următoarele L linii sunt câte C numere întregi, separate prin câte un spaţiu, reprezentând elementele matricei.

Date de ieșire

Prima linie a fişierului left.out va conţine un singur număr întreg, reprezentând suma maximă cerută.

Restricții și precizări

2 ≤ L,C ≤ 1000
Valorile din matrice sunt numere întregi pe 32 de biţi.
Rezultatul este un număr întreg pe 32 de biţi.
Suma elementelor oricărei submatrice este un număr întreg pe 32 de biţi.

Exemplu

left.in

left.out

Explicație

De pe prima linie se aleg 3 numere iar de pe celelalte linii câte 2 numere.

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 Left:

#include <fstream>
#include <cstring>
using namespace std;
#define DIM 1011

int A[DIM], B[DIM], C[DIM], AA[DIM], BB[DIM], CC[DIM];
int V[DIM], W[DIM];
int N, M, i, j, mx, x;

inline int maxim(int a, int b){
    if (a>b)
        return a;
    return b;
}

int main(){
    ifstream f("left.in");
    ofstream g("left.out");
    f>>N>>M;
    for (j=1;j<=M;j++) {
        f>>x;
        V[j] = V[j-1] + x;
    }
    for (j=1;j<=M;j++) {
        f>>x;
        W[j] = W[j-1] + x;
        if (j==1) {
            B[j] = V[j] + W[j];
            C[j] = V[j+1] + W[j];
        } else 
            if (j==M) {
                A[j] = V[j-1] + W[j];
                B[j] = V[j] + W[j];
            } else {
                A[j] = V[j-1] + W[j];
                B[j] = V[j] + W[j];
                C[j] = V[j+1] + W[j];
            }
    }
    
    for (i=3;i<=N;i++) {
        memcpy(AA, A, sizeof(A));
        memcpy(BB, B, sizeof(B));
        memcpy(CC, C, sizeof(C));
        for (j=1;j<=M;j++) {
            f>>x;
            W[j] = W[j-1] + x;
            if (j==1) {
                B[j] = W[j] + CC[j];
                C[j] = W[j] + maxim(AA[j+1], BB[j+1]);
            } else
                if (j==M) {
                    A[j] = W[j] + maxim(BB[j-1], CC[j-1]);
                    B[j] = W[j] + AA[j];
                } else {
                    A[j] = W[j] + maxim(BB[j-1], CC[j-1]);
                    B[j] = W[j] + maxim(AA[j], CC[j]);
                    C[j] = W[j] + maxim(AA[j+1], BB[j+1]);
                }
        }
    }
    
    f.close();
    
    mx = maxim(maxim(B[1], C[1]), maxim(A[M], B[M]));
    for (i=2;i<M;i++)
        if (mx < maxim(maxim(A[i], B[i]), C[i]))
            mx = maxim(maxim(A[i], B[i]), C[i]);
        
    
    g<<mx;
    g.close();
    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 #738 Left

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