首页 > 试题广场 >

矩阵

[编程题]矩阵

矩阵 M 包含 R 行 C 列，第 i 行第 j 列的值为 M_i,_j。
请寻找一个子矩阵，使得这个子矩阵的和最大，且满足以下三个条件：
子矩阵的行数不能超过 X 行。
子矩阵的列数不能超过 Y 列。
子矩阵中 0 的个数不能超过 Z 个。
请输出满足以上条件的最大子矩阵和。

第一行输入五个整数 R，C，X，Y，Z。
接下来 N 行，每行输入 M 个整数，第 i 行第 j 列的整数表示 M_i,_j。
1 ≤ R,C ≤ 500.
1 ≤ X ≤ R.
1 ≤ Y ≤ C.
1 ≤ Z ≤ R x C.
-10⁹≤  M_i,j≤ 10⁹

输出满足以上条件的最大子矩阵和。

示例1

输入

5 5 3 3 4
0 0 10 0 0
3 4 0 2 3
-1 3 0 -8 3
0 0 32 -9 3
3 0 45 3 0

示例2

2 2 2 2 2
-1 -1
-1 -1

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

枚举单调队列单调栈

上传者：牛客301599号

难度：

0条回答 0收藏 107浏览

查看代码

矩阵

扫一扫，把题目装进口袋