博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Luogu1681_ 最大正方形II
阅读量:5878 次
发布时间:2019-06-19

本文共 2010 字,大约阅读时间需要 6 分钟。

题目背景

忙完了学校的事,v神终于可以做他的“正事”:陪女朋友散步。一天,他和女朋友走着走着,不知不觉就来到了一个千里无烟的地方。v神正要往回走,如发现了一块牌子,牌子上有有一行小字和一张图,小字说道:“找到图上最大的交错正方形之后和我联系,这块地就是你的了。”在房价疯长的年代,v神当然不愿错过这个机会,于是开始找了起来……以v神的能力当然找不出来了,你能帮v神找出来吗?

题目描述

图上有一个矩阵,由N*M个格子组成,这些格子由两种颜色构成,黑色和白色。请找到面积最大的且内部是黑白交错(即两个相连的正方形颜色不能相同)的正方形。

输入格式:

第一行两个整数N和M,分别表示行数和列数。接下来有N行,每行M个数,0或1分别表示这个格子是黑色或白色。

输出格式:

仅有一行,表示满足条件最大正方形的 边长

样例

INPUT

3 3

0 1 0
1 0 0
1 1 1

OUTPUT

2

HINT

样例解释:

(1,1)到(2,2)这个正方形是满足条件的,它的边长是2

数据范围约定:

对于30%的数据,\(N\leq20\)

对于60%的数据,\(N\leq300\)

对于100%的数据,\(N\leq1500\)

SOLUTION

题解:dp

一看数据范围就知道是\(O(n^2)\)的算法,再说了这题如果要暴力的话最暴力的可以达到\(O(n^6)\)之高。(有没有其他暴力我不知道qwq)

所以考虑通过题目的性质进行优化。

根据题意,正方形的合法与否在于相邻格子之间关系的合法与否。所以我们可以先处理左右之间关系,在处理上下之间的关系。这里就可以用\(lft[i][j],rgt[i][j]\)数组在同一层扫一遍时维护一下第\(i\)\(j\)个格子最左/右可以延伸到哪一格,这里注意一下维护顺序,\(lft[][]\)数组是从左到右,而\(rgt[][]\)是从右到左。

然后处理上下层之间的关系就可以直接进行层与层之间的转移了

\[lft[i][j]=max(lft[i][j],lft[i-1][j])\]
\[rgt[i][j]=min(rgt[i][j],rgt[i-1][j])\]
\[hgt[i][j]=hgt[i-1][j]+1\]

这个\(hgt\)指的是高度(纵向长度)

然后维护过程中顺带记录一下最大值就可以了

#include 
#include
#include
#include
using namespace std;const int N=1510;int n,m,hgt[N][N],sq[N][N],lft[N][N],rgt[N][N];int main(){ int i,j; scanf("%d%d",&n,&m); for (i=1;i<=n;++i) for (j=1;j<=m;++j){ scanf("%d",&sq[i][j]); lft[i][j]=j;rgt[i][j]=j;hgt[i][j]=1; } for (i=1;i<=n;++i) for (j=2;j<=m;++j) if (sq[i][j]^sq[i][j-1]) lft[i][j]=lft[i][j-1]; for (i=1;i<=n;++i) for (j=m-1;j>=1;--j) if (sq[i][j]^sq[i][j+1]) rgt[i][j]=rgt[i][j+1]; int ans=0; for (i=1;i<=n;++i) for (j=2;j<=m;++j){ if (i>1&&(sq[i][j]^sq[i-1][j])){ lft[i][j]=max(lft[i][j],lft[i-1][j]); rgt[i][j]=min(rgt[i][j],rgt[i-1][j]); hgt[i][j]=hgt[i-1][j]+1; } int a=min(rgt[i][j]-lft[i][j]+1,hgt[i][j]); ans=max(ans,a); } printf("%d\n",ans); return 0;}

转载于:https://www.cnblogs.com/hkpls/p/9790848.html

你可能感兴趣的文章
开发完第一版前端性能监控系统后的总结(无代码)
查看>>
Python多版本情况下四种快速进入交互式命令行的操作技巧
查看>>
MySQL查询优化
查看>>
【Redis源码分析】如何在Redis中查找大key
查看>>
android app启动过程(转)
查看>>
安装gulp及相关插件
查看>>
如何在Linux用chmod来修改所有子目录中的文件属性?
查看>>
Applet
查看>>
高并发环境下,Redisson实现redis分布式锁
查看>>
关于浏览器的cookie
查看>>
Hyper-V 2016 系列教程30 机房温度远程监控方案
查看>>
.Net 通过MySQLDriverCS操作MySQL
查看>>
JS Cookie
查看>>
ubuntu Unable to locate package sysv-rc-conf
查看>>
笔记:认识.NET平台
查看>>
cocos2d中CCAnimation的使用(cocos2d 1.0以上版本)
查看>>
【吉光片羽】短信验证
查看>>
MacBook如何用Parallels Desktop安装windows7/8
查看>>
gitlab 完整部署实例
查看>>
GNS关于IPS&ASA&PIX&Junos的配置
查看>>