Como fazer MATRIZE dentro de MATRIZE?
Dada uma matriz A, determinar a maior quantidade de elementos de uma submatriz
super-legal da matriz A.
Entrada
A primeira linha contém dois inteiros L e C indicando respectivamente o número de linhas e o
número de colunas da matriz. Cada uma das L linhas seguintes contém C inteiros Xi representando
os elementos da matriz.
Saída
Seu programa deve produzir uma única linha, com apenas um número inteiro, a maior quantidade
de elementos de uma submatriz super-legal da matriz da entrada, ou zero no caso de não existir
uma submatriz super-legal.
Restrições
• 2 ≤ L; C ≤ 1000
• −106 ≤ Xi ≤ 106
Exemplo de entrada 1
3 3
1 4 10
5 2 6
11 1 3
Exemplo de saída 1
9
Exemplo de entrada 2
3 3
1 3 1
2 1 2
1 1 1
Exemplo de saída 2
4
super-legal da matriz A.
Entrada
A primeira linha contém dois inteiros L e C indicando respectivamente o número de linhas e o
número de colunas da matriz. Cada uma das L linhas seguintes contém C inteiros Xi representando
os elementos da matriz.
Saída
Seu programa deve produzir uma única linha, com apenas um número inteiro, a maior quantidade
de elementos de uma submatriz super-legal da matriz da entrada, ou zero no caso de não existir
uma submatriz super-legal.
Restrições
• 2 ≤ L; C ≤ 1000
• −106 ≤ Xi ≤ 106
Exemplo de entrada 1
3 3
1 4 10
5 2 6
11 1 3
Exemplo de saída 1
9
Exemplo de entrada 2
3 3
1 3 1
2 1 2
1 1 1
Exemplo de saída 2
4
Leonardo Delmondes
Curtidas 0
Respostas
Sadasd
16/08/2019
O que seria uma matriz super-legal?
GOSTEI 0
Leonardo Delmondes
16/08/2019
é indicado como isso " Denotando por Ai;j o elemento na i-ésima linha e j-ésima coluna da matriz A, dizemos que uma
matriz é “legal” se a condição. "
matriz é “legal” se a condição. "
GOSTEI 0
Leonardo Delmondes
16/08/2019
Mas precisamente assim:
Denotando por Ai;j o elemento na i-ésima linha e j-ésima coluna da matriz A, dizemos que uma
matriz é “legal” se a condição
A1;1 + Alin;col ≤ A1;col + Alin;1
é verdadeira para todo lin > 1 e col > 1.
Adicionalmente, dizemos que a matriz é “super-legal” se cada uma de suas submatrizes com pelo
menos duas linhas e duas colunas é legal. Lembre que uma submatriz S de uma matriz ML×C é uma
matriz que inclui todos os elementos Mi;j tais que l1 ≤ i ≤ l2 e c1 ≤ j ≤ c2, para 1 ≤ l1 ≤ l2 ≤ L e
1 ≤ c1 ≤ c2 ≤ C
Denotando por Ai;j o elemento na i-ésima linha e j-ésima coluna da matriz A, dizemos que uma
matriz é “legal” se a condição
A1;1 + Alin;col ≤ A1;col + Alin;1
é verdadeira para todo lin > 1 e col > 1.
Adicionalmente, dizemos que a matriz é “super-legal” se cada uma de suas submatrizes com pelo
menos duas linhas e duas colunas é legal. Lembre que uma submatriz S de uma matriz ML×C é uma
matriz que inclui todos os elementos Mi;j tais que l1 ≤ i ≤ l2 e c1 ≤ j ≤ c2, para 1 ≤ l1 ≤ l2 ≤ L e
1 ≤ c1 ≤ c2 ≤ C
GOSTEI 0