题目描述
一个N×M的矩阵，找出这个矩阵中所有元素的和不小于K的面积最小的子矩阵（矩阵中元素个数为矩阵面积）
输入格式
每个案例第一行三个正整数N,M<=100，表示矩阵大小，和一个整数K。接下来N行，每行M个数，表示矩阵每个元素的值
输出
输出最小面积的值。如果出现任意矩阵的和都小于K，直接输出-1。
样例输入
4 4 10
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 3 15
10 -5 10
样例输出
1
3
若有解决，万分感激！ 因为你把我们整个学校的OIER们都拯救了！！
http://www.rqnoj.cn/Discuss_Show.asp?DID=12763
6 条评论
-
dapper LV 4 @ 2013-10-27 11:34:06
for i:=1 to n do//每行
for l:=1 to m do//左侧
for r:=l to m do//右侧
三重循环把每一行的各个矩形都枚举出来（也就是高度为1的矩形），并把元素和保存在f数组中
然后for j:=1 to m do//每列
for t:=1 to n do//上端
for b:=t to n do//下端
三重循环，根据f数组中的值来枚举矩形，同时和ans比较取min，最后输出即可-
@ 2013-11-04 00:28:32
你认为O(N^6)对这题的100有用吗
求n^3算法
-
-
@ 2013-10-26 21:11:44
这道题官方数据绝对有问题。我昨天交的那个其实没考虑到一个问题。
-
@ 2013-10-26 12:55:39
我用P转C成功了！！！！！！！
哈哈哈哈 -
@ 2013-10-26 11:56:46
VIJOSp1255月饼盒，是求最大子矩阵，稍加改变即可
-
@ 2013-10-26 11:52:11
吴永基很给力的、、、、
我用O^3都没过、、、超时的说 -
@ 2013-10-26 09:35:37
P.S暴力枚举（O(N^6)）过不了，但我们学校已经有人过了！！唯一的一个！！
求大神给个更好的思路！！
而且，我只会FP。。-
@ 2013-10-26 12:56:09
我用P转C成功了！！！！！！！
哈哈哈哈
-
- 1
