Code[VS]1159 最大全0子矩阵
2023-09-27 14:28:32 时间
原题链接:http://codevs.cn/problem/1159/
题目描述 Description
在一个0,1方阵中找出其中最大的全0子矩阵,所谓最大是指O的个数最多。
输入描述 Input Description
输入文件第一行为整数N,其中1<=N<=2000,为方阵的大小,紧接着N行每行均有N个0或1,相邻两数间严格用一个空格隔开。
输出描述 Output Description
输出文件仅一行包含一个整数表示要求的最大的全零子矩阵中零的个数。
样例输入 Sample Input
5
0 1 0 1 0
0 0 0 0 0
0 0 0 0 1
1 0 0 0 0
0 1 0 0 0
样例输出 Sample Output
9
题解
悬线法模板题。
对于每个点,我们维护一下该点向上最大能扩展多少,以及这个点的悬线向左向右能平移多少,然后枚举所有悬线求最大子矩形即可,复杂度 O(nm) O ( n m ) 。
代码
#include<bits/stdc++.h>
using namespace std;
const int M=2e3+5;
int n,h[M][M],l[M][M],r[M][M],sq[M][M];
void in()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%d",&sq[i][j]);
}
void ac()
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
h[i][j]=sq[i-1][j]?1:h[i-1][j]+1,
l[i][j]=sq[i][j-1]?1:l[i][j-1]+1;
for(int j=n;j>=0;--j)
r[i][j]=sq[i][j+1]?1:r[i][j+1]+1;
}
int ans=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
if(sq[i][j]){h[i][j]=l[i][j]=r[i][j]=0;continue;}
if(i>1&&!sq[i-1][j])
l[i][j]=min(l[i][j],l[i-1][j]),
r[i][j]=min(r[i][j],r[i-1][j]);
ans=max(ans,(l[i][j]+r[i][j]-1)*h[i][j]);
}
printf("%d",ans);
}
int main()
{
in();ac();
return 0;
}
相关文章
- 在VS Code中对Python进行单元测试
- 在macOS下正确配置 VS Code 使用 virtualenv 里的 python 环境参数
- VS Code摸鱼神器,让你快速开发AI模型
- 【VS开发】MFC学习之 解决StretchBlt()图片缩放绘图失真
- 【VS开发】【编程开发】【C/C++开发】结构体中的数组与指针的内存分配情况说明
- 【VS开发】Caffelib中出现的问题:强制链接静态库所有符号(包括未被使用的)
- 7月8日科技资讯|任正非:华为鸿蒙将比安卓快 60%;小米回应主题侵权;VS Code 1.36发布
- 7月5日科技资讯|百度回应“抄袭天猫精灵”;ofo 押金退完需 12 年;VS Code 1.36 发布
- 8月14日科技资讯|阿里平头哥研发专用 SoC 芯片;部分 MacBook Pro 被禁止上飞机;VS Code 1.37 发布
- angular cli, vs code liveserver, vs 2019 iis express 10, vs code kestrel 使用 https + ip
- 静态库 VS 动态库
- 美国主机BlueHost vs HostEase
- 【文心一言 vs. 通义千文】一言对千问:自百度之后,阿里终于还是出手了——通义千问
- Facebook 默认开发环境采用 VS Code
- VS Code 快捷键(中英文对照版)
- VS Code 插件
- vs code 安装
- vs 添加快捷键 | 修改快捷键、添加注释、添加快速插入代码(使用#if 0 注释)
- Code[VS]2549 自然数和分解
- 激光SLAM Vs 视觉SLAM
- 解决 VS 跳转定义和 Resharper 重复
- 使用VS Code 从零开始开发并调试.NET Core 应用程序
- 搭建 Markdown 强大写作环境-VS Code
- authentication vs authorization 验证与授权的区别