AcWing 3887. 最大0矩阵
原题链接
简单
作者:
罚时大师
,
2024-02-21 09:37:54
,
所有人可见
,
阅读 37
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const short N = 2001;
char a[N];
short n;
short up[N];
short l[N], r[N];
int ans;
short i, j;
/*
悬线法, 枚举每个点作为矩形的底部最大能延伸的长度 up[i] if (a[i)) up[i] = 0; else up[i] = up[i - 1] + 1;
枚举每根线往左能走的最大距离 l[i][j], if (up[i][j] > 1 ) l[i][j] = min(l[i - 1][j], num) else l[i][j] = num
num 表示一个点作为右边界的最大连续零的长度, 这在枚举用变量即可。 然后二维可以优化为一维
往右走同理
*/
signed main()
{
cin >> n;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
cin >> a[j];
if (a[j] == '1')
up[j] = 0;
else
up[j] += 1;
}
short s = 0;
for (int j = 1; j <= n; j++)
{
if (a[j] == '1') s = 0;
else s++;
if (up[j] > 1) l[j] = min(l[j], s);
else l[j] = s;
}
s = 0;
for (int j = n; j >= 1; j--)
{
if (a[j] == '1') s = 0;
else s++;
if (up[j] > 1) r[j] = min(r[j], s);
else r[j] = s;
ans = max(ans, (int)up[j] * (l[j] + r[j] - 1));
}
}
cout << ans << "\n";
return 0;
}