P5150: 牛宫-训练套题T1T2
传统题
5.000s
时间限制
128MB
内存限制
3 提交
3 解决
【题目描述】
2. 牛宫[long.pas/
long.c/ long.cpp]
【问题描述】
AP神牛准备给自己盖一座很华丽的矩形宫殿。于是，他看中了一块
N*M的矩形空地。空地中每个格子都有自己的海拔高度。
AP想让他的宫殿的平均海拔在海平面之上
>=0（假设海平面的高度是
0，平均数都会算吧？）。而且，
AP希望他的宫殿尽量大，能够容纳更多的人来膜拜他。请问
AP的宫殿最后会有多大。
【输入数据】
第一行为
N和
M。之后
N行，每行
M个数，描述的空地的海拔。
【输出数据】
输出一行
,表示宫殿最大面积。
【输入样例】
3 2
4 0
-10 8
-2 -2
【输出样例】
4
【数据规模】
对于
30%的数据，
N,M≤
50;
对于
100%的数据，
N,M≤
200；
【提示】
题意简述
求一个矩阵中平均数大等于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)。并且记下过程中最大的原始位置值，看是否能够更新最优解。