[Login|Register]
Problems

Status

Rank

Problem 1276
最大子矩阵
Time Limit: 1000ms
Memory Limit: 65536kb
Description
相信大家都做过传说中“To the max”这题吧,大致描述如下:
给你一个全部由数字组成的大小为N*M的矩阵,该矩阵包含了若干个子矩阵,定义子矩阵的和为该子矩阵中所有数字之和,我们可以通过比较所有子矩阵,找出最大子矩阵的和。
例如有如下一个矩阵:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
那么最大子矩阵和为15,对应子矩阵为:
9 2
-4 1
-1 8
相信大家都能快速求解出该问题。其实想一想,还可以求出满足子矩阵和最大的子矩阵的个数(如上例中只有1个子矩阵和为15且最大)。
亲,相信难不到你们的!!!
Input
第一行输入一个数T(T<=20),代表下面将有T组测试数据。每组测试数据包括两部分:
第一部分:两个正整数N,M (0<N,M<=100),分别矩阵的行和宽。
第二部分:一个N*M的数字矩阵,该矩阵中每个数字的范围为[-10000, 10000]。
Output
针对每组测试数据,输出最大子矩阵和、最大子矩阵的个数。用空格隔开。
Sample Input
1
2 3
0 0 0
0 0 0 
Sample Output
0 18
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.3ms with 1 query(s).