「codecomb2093」牛宫
Description
Hzgd神牛准备给自己盖一座很华丽的宫殿。于是，他看中了一块N*M的矩形空地。空地中每个格子都有自己的海拔高度。胡张想让他的宫殿的平均海拔在海平面之上（假设海平面的高度是0，平均数都会算吧？）。而且，胡张希望他的宫殿是个矩形且尽量大，能够容纳更多的人来膜拜他。请问胡张的宫殿最后会有多大？
Input Format
第一行为N和M。之后N行，每行M个数，描述的空地的海拔。
Output Format
输出一行,表示宫殿最大面积。
|
1 |
Sample Input |
|
1 |
3 2 |
|
1 |
4 0 |
|
1 |
-10 8 |
|
1 |
-2 -2 |
Sample Output
|
1 |
4 |
Data Limit
对于30%的数据，N,M≤50;
对于100%的数据，N,M≤200；
题解
先n^2枚举矩形的左右两边l-r，然后在行上找最值
我们可以得到前i行l-r的总和。。记为si
如果si>sj且i>j则(i-j)*(r-l+1)可以更新答案
维护单调递减栈每次在其中二分找j
或者将si为关键字排序，然后扫描一遍边维护i的最小值边更新答案
复杂度都是n^3logn
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ans,top; int f[205]; ll a[205][205],st[205],sum[205]; int find(ll x) { int l=1,r=top; int ans=-1; while(l<=r) { int mid=(l+r)>>1; if(st[mid]<x)ans=mid,r=mid-1; else l=mid+1; } return ans; } void solve(int x,int y) { top=0; for(int i=1;i<=n;i++) sum[i]+=a[i][y]; st[0]=9000000000000000000; ll tmp=0; for(int i=1;i<=n;i++) { tmp+=sum[i]; if(tmp>0)ans=max(ans,i*(y-x+1)); else { int t=find(tmp); if(t!=-1)ans=max(ans,(i-f[t])*(y-x+1)); } if(tmp<st[top]) { st[++top]=tmp; f[top]=i; } } } int main() { n=read();m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(); for(int i=1;i<=m;i++) { memset(sum,0,sizeof(sum)); for(int j=i;j<=m;j++) solve(i,j); } printf("%d",ans); return 0; } |
Subscribe
计数器 9786143
OI 课件=>
OI 课件=>