扫描线-小Z的桌子
2024-08-30 07:37:19
大概题意:在一个01矩阵中找到一个周长最大的全0矩形。
这道题用的是扫描线,O(n^2),求最大面积的思路完全可以放在这里。下面说说思路。
首先,一个最大周长子矩形(最大周长全0矩形),左右两侧的列上一定至少有一个1,不然显然这个矩形可以再往左/右扩展。
由于这个,我们联想到找矩形两边的1。初始想法是先n方,预处理一个点上面有多少点,下面有多少点。枚举出每一行的每一段连续的0,将这些每个点的up和down加起来减1,取min,这就是这个可能最大周长子矩形的最大可能高。答案即是高+宽乘2。
但是,这种做法有几个小问题,以后做扫描线的题目时一定要注意:
1.初始想法中直接统计最小高的想法是错的。例如:
4 5
XX.XX
XX.XX
X...X
X.X.X
显然,应该分别统计minup和mindown。
2.两个边界上的1不一定在同一行,例如:
.
X.
.X
.
.
但是,我们一定可以保证它一定紧贴一边的x,所以我们只需统计0序列的所有前缀即可。
这样就没有错了
最新文章
- POJ 1474 Video Surveillance(半平面交)
- 用jstl截取字符串
- aspx页面Page_Load和aspx页面上控件Page_Load事件执行顺序
- 串行通讯之.NET SerialPort异步写数据
- 设置Session的超时时间
- Android开发框架SmartAndroid2.0 强劲框架
- CSS3学习系列之选择器(二)
- Qt creator中文输入—fctix-qt5 源码编译 libfcitxplatforminputcontextplugin.so
- 整理关于web项目如何防止CSRF和XSS攻击的方法
- Mysql基准测试详细解说(根据慕课网:《打造扛得住Mysql数据库架构》视频课程实时笔录)
- Enterprise architect 类图加时序图
- Codeforces Round #496 (Div. 3)
- Maya中输出alembic文件的方法
- 《ASP.NET MVC企业实战》(一) MVC开发前奏
- 吴恩达-coursera-机器学习-week10
- 转:NGNIX模块开发——nginx的配置系统
- mysql错误号代表的含义
- Push rejected: Push master to origin/master was rejected /failed to push some refs to /git did not exit cleanly
- shiro web 集成
- 为什么S/4HANA的销售订单创建会触发生产订单的创建