Fie A o matrice dreptunghiulară de numere întregi cu N linii numerotate de la 1 la N şi M coloane numerotate de la 1 la M. În matricea A oricare două elemente consecutive de pe aceeaşi linie sunt distincte.
Se defineşte un şir valid de numere întregi ca fiind fie un şir crescător, fie un şir descrescător, fie un şir crescător concatenat cu un şir descrescător, fie un şir descrescător concatenat cu unul crescător. Exemple de şiruri valide sunt: 1 2 3 7, 8 5 2 1, 3 5 6 2, 4 1 5 6.
Se defineşte o submatrice a lui A de coordonate (l1, c1, l2, c2) ca fiind matricea formată din toate elementele A(i,j), cu l1 ≤ i ≤ l2 şi c1 ≤ j ≤ c2.
O submatrice a lui A este validă dacă liniile sale sunt şiruri valide.
Atenţie! O submatrice validă poate avea pe o linie un şir crescător de numere, pe a doua un şir descrescător, pe a treia un şir crescător concatenat cu unul descrescător etc. Deci, liniile unei submatrice valide nu trebuie să fie neapărat şiruri de acelaşi tip.
Aria unei submatrice este egală cu numărul de elemente din care este formată submatricea.

Cerința

Se cere să se găsească o submatrice validă a lui A de arie maximă.

Date de intrare

Fișierul de intrare matrice9.in conține pe prima linie numerele N şi M, separate prin spaţiu. Pe fiecare dintre următoarele N linii se află câte M numere întregi separate prin câte un spaţiu, reprezentând elementele matricei A.

Date de ieșire

Fișierul de ieșire matrice9.out va conţine o singură linie pe care vor fi scrise coordonatele l1, c1, l2, c2 (în această ordine şi separate prin câte un spaţiu) ale unei submatrice valide de arie maximă. În cazul în care există mai multe soluţii cu arie maximă, se va afişa oricare dintre ele.

Restricții și precizări

1 ≤ N, M ≤ 1000
70% din teste vor avea N, M ≤ 600
Elementele matricei A sunt numere întregi din intervalul [-30000, 30000].

Exemplu

matrice9.in

2 6
1 2 5 7 9 10
3 4 3 5 1 10

matrice9.out

1 1 2 3

Explicație

Aria maximă este 6. O altă soluţie de arie maximă ar putea fi 1 1 1 6 sau 1 2 2 4 sau 1 3 2 5 sau 1 4 2 6.

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

#include <bits/stdc++.h>
#define N_MAX           1024
#define SEQ_UNKNOWN     0
#define SEQ_INCREASING  1
#define SEQ_DECREASING  2
using namespace std;

int N, M;
int A[N_MAX][N_MAX];

int Height[N_MAX], Type[N_MAX], Start[N_MAX];
int Count, Stack[N_MAX], Top[N_MAX];

int Best, Best1l, Best1c, Best2l, Best2c;

void solve ()
{
   int i, j, top;

   for (j = 0; j < M; j++)
   {
      for (i = 0; i <= N; i++)
      {
         // Get the height of the column
         if (i == N)
            Height[i] = 0;
         else if (j == 0)
            Height[i] = 1;
         else if (Type[i] == SEQ_UNKNOWN)
     {
        Type[i] = (A[i][j] > A[i][j - 1]) ? SEQ_INCREASING : SEQ_DECREASING;
            Height[i]++;
         }
         else if (Type[i] == SEQ_INCREASING)
         {
            if (A[i][j] < A[i][j - 1])
            {
               Height[i] = j - Start[i] + 1;
               Start[i] = j - 1;
               Type[i] = SEQ_DECREASING;
            }
            else
               Height[i]++;
         }
         else if (Type[i] == SEQ_DECREASING)
         {
            if (A[i][j] > A[i][j - 1])
            {
               Height[i] = j - Start[i] + 1;
               Start[i] = j - 1;
               Type[i] = SEQ_INCREASING;
            }
            else
               Height[i]++;
         }

         // Do the stack thing
         top = i;
         while (Count > 0 && Height[i] <= Stack[Count - 1])
         {
            top = Top[Count - 1];
            if (Stack[Count - 1] * (i - top) > Best)
            {
               Best = Stack[Count - 1] * (i - top);
           Best1l = top;
           Best2l = i - 1;
           Best1c = j - Stack[Count - 1] + 1;
               Best2c = j;
            }
            Count--;
         }
         if (Height[i] > 0)
         {
            Stack[Count] = Height[i];
            Top[Count++] = top;
         }
      }
   }

   printf("%d %d %d %d\n", Best1l + 1, Best1c + 1, Best2l + 1, Best2c + 1);
}

void read_solve ()
{
   int i, j;

   freopen("matrice9.in", "r", stdin);
   freopen("matrice9.out", "w", stdout);
   scanf("%d%d", &N, &M);
   for (i = 0; i < N; i++)
      for (j = 0; j < M; j++)
         scanf("%d", &A[i][j]);

   solve();
}

int main ()
{
   read_solve();
   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 #2429 matrice9

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