2675 问题 D: 蓝桥杯2022年第十三届省赛真题-最大子矩阵

时间限制: 1s 内存限制: 512MB 提交: 1695 解决: 163
题目描述

小明有一个大小为 N × M 的矩阵,可以理解为一个 N 行 M 列的二维数组。 我们定义一个矩阵 m 的稳定度 f(m) 为 f(m) = max(m) − min(m),其中 max(m) 表示矩阵 m 中的最大值,min(m) 表示矩阵 m 中的最小值。现在小明想要从这个矩阵中找到一个稳定度不大于 limit 的子矩阵,同时他还希望这个子矩阵的面积越大越好(面积可以理解为矩阵中元素个数)。

子矩阵定义如下:从原矩阵中选择一组连续的行和一组连续的列,这些行列交点上的元素组成的矩阵即为一个子矩阵。 

输入

第一行输入两个整数 N,M,表示矩阵的大小。

接下来 N 行,每行输入 M 个整数,表示这个矩阵。

最后一行输入一个整数 limit,表示限制。 

输出
输出一个整数,分别表示小明选择的子矩阵的最大面积。 
样例输入
3 4
2 0 7 9
0 6 9 7
8 4 6 4
8
样例输出
6
提示

满足稳定度不大于 8 的且面积最大的子矩阵总共有三个,他们的面积都是 6(粗体表示子矩阵元素):

2 0 7 9
0 6 9 7
8 4 6 4

2 0 7 9
0 6 9 7
8 4 6 4

2 0 7 9
0 6 9 7
8 4 6 4

蓝桥杯2022年第十三届省赛真题最大子矩阵
对于所有评测用例,0 ≤ 矩阵元素值, limit ≤ 105


比赛公告

第十三届蓝桥杯大赛软件赛省赛 Java 大学 B 组
C题

字符统计

D题

最少刷题数

E题

求阶乘

F题

最大子矩阵

G题

数组切分

H题

回忆迷宫

I题

红绿灯

J题

拉箱子

注意事项:

1. 不要使用 package 语句。

2. 选手代码的主类名必须为:Main,否则会被判为无效代码。

3. 如果程序中引用了类库,在提交时必须将 import 语句与程序的其他部分同时提交。

4. 只允许使用 Java 自带的类库。

5. 提交时,注意选择使用Java语言。


本比赛结束依旧可以训练,见题集2022年第十三届蓝桥杯大赛软件类省赛Java大学B组真题