P1565牛宫

dinglinxi0409 · 2021-07-21 11:28:15 · 题解

直接暴力枚举就可以了。

#include <bits/stdc++.h>
using namespace std;
long long a[201][201],sum[201][201];
int main()
{
    long long ans=0,z=0;
    int m,n,i,j,x,y;
    cin>>n>>m;
    for (i=1;i<=n;i++) for (j=1;j<=m;j++) {cin>>a[i][j]; sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];} //输入和预处理
    for (i=1;i<=n;i++) for (j=1;j<=m;j++) for (x=i;x<=n;x++) for (y=j;y<=m;y++) //暴力枚举
        if (!(sum[x][y]+sum[i-1][j-1]-sum[x][j-1]-sum[i-1][y]<=0)) //如果平均海拔在海平面以上
            if ((z=(long long)(x-i+1)*(y-j+1))>=ans) ans=z; //如果面积比原来的最大面积大，那么就更新最大面积
    cout<<ans<<endl; //输出最大面积
    return 0;
}