问题 5308 --牛宫-训练套题T1T2

5308: 牛宫-训练套题T1T2

时间限制: 5 Sec  内存限制: 128 MB
提交: 19  解决: 10
[提交][状态][讨论版][命题人:]

题目描述

2. 牛宫[long.pas/ long.c/ long.cpp]

【问题描述】

AP神牛准备给自己盖一座很华丽的矩形宫殿。于是,他看中了一块N*M的矩形空地。空地中每个格子都有自己的海拔高度。AP想让他的宫殿的平均海拔在海平面之上>=0(假设海平面的高度是0,平均数都会算吧?)。而且,AP希望他的宫殿尽量大,能够容纳更多的人来膜拜他。请问AP的宫殿最后会有多大。

【输入数据】

第一行为NM。之后N行,每行M个数,描述的空地的海拔。

【输出数据】

输出一行,表示宫殿最大面积。

【输入样例】

3 2
4 0
-10 8
-2 -2

【输出样例】

4

【数据规模】

对于30%的数据,N,M50;

对于100%的数据,N,M200

提示






题意简述





        求一个矩阵中平均数大等于0的最大子矩阵的面积。








解题思路


       首先,平均数大于等于0等价于和大于等于0,这样便于处理。


方法1:O(N^6)枚举获得部分分。


方法2:针对问题特点改进


       二维问题常常可以转为一维来处理,对于一维问题就比较容易思考。


       注意到题目要求的是“和”,因此如果将连续若干行的每列分别相加求和变为一行,并不会影响到求解。






枚举连续行的组合,将二维矩阵压缩为了一维的数列。即将问题转化为在一行数中找出连续和大等于0的最长的一段。


       如何快速求得一行数中连续和大等于0的最长的一段?


       常用的连续和计算方法:是先预处理出前i个数的和sum[i],则sum[i,j]=sum[j]-sum[i-1]。


       由于条件是sum[i,j]>=0,不妨尝试把sum数组计算出来,再对它进行研究。




假设已知最优区间是从第一个数开始,我们要找出它的右边界。则以i为右边界的区间的和即为sum[i]。易知当sum[i]>=0时状态合法,而i最大则为最优。


       当然,最优区间不一定是从第一个数开始的。假设最优区间的左边界为t,则此时以i为右边界的区间的和即为sum[i]-sum[t-1],枚举i与t,从其中找出大等于0的最长的区间(长度为i-t+1)。


       尽管效率提高至o(n^4),但还是不够优?没有用好题目中只需大等于0的条件。






再一次注意观察sum数组。考虑固定右界i,如果左界t与t+1的sum值均为合法解,则t+1的合法解时必然不如t优(因为左边界不断往右移动,而右边界不变,区间变短)。反之,对于固定的左界t,只需找到sum(i)>=sum(t)的最大右界值即可,这就具有了某种意义上的单调性。能否利用呢?


        将sum按照从大到小排序(注意需要保留原始位置的信息),并且设定一个头指针指向排序后的sum数组队头。枚举左边界,即每次移动左边界后,右界通过检查指针指向的sum值。


       如果指向的sum值减去左界的sum值合法了,则不断向后移,直到相减<0。






在移动过程中找出原始位置最后面的,看是否能够更新最优值。(注意需要将区间长度乘以压缩的行数才是面积)至此,问题得到比较好的解决。


   算法简述


   1、枚举连续行,压缩为一维 ;


   2、在一维区间中求出sum数组(sum[i]=sum[i-1]+num[i],sum[0]=0),并且记下每个sum值的原始位置;


   3、将sum快排(注意需要保留原始位置的信息),形成队列,设head=1;


   4、从0至n-1枚举left,while sum[head]-sum[left]>=0 do inc(head)。并且记下过程中最大的原始位置值,看是否能够更新最优解。









来源

 

[提交][状态]