Luogu1681_ 最大正方形II
题目背景
忙完了学校的事,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[][]\)是从右到左。
然后处理上下层之间的关系就可以直接进行层与层之间的转移了
\]
\]
\]
这个\(hgt\)指的是高度(纵向长度)
然后维护过程中顺带记录一下最大值就可以了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
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;
}
最新文章
- PullToRefreshListView相关
- 在​W​C​F​中​使​用​消​息​队​列​M​S​M​Q
- jquery-easyui-tree异步树
- 15天玩转redis —— 第八篇 你不得不会的事务玩法
- 用ProGet搭建内部的NuGet服务器(更新安装步骤)
- VVDocumenter升级后不能使用问题
- android app性能优化大汇总(google官方Android性能优化典范 - 第2季)
- C++ Vector
- Android HelloChart Demo
- 12.引入依赖项目的时候,如果找不到jar
- 【实验吧】CTF_Web_登录一下好吗?
- SQLServer之创建提交读
- February 12th, 2018 Week 7th Monday
- React Native之code-push的热更新(ios android)
- 解决centos7命令行中文乱码
- shell脚本遍历当前目录下以数字命名的目录,并打印
- java多线程快速入门(十五)
- 导航,头部,CSS基础
- Linux软件源书写格式解析及本地yum源制作
- Big Problems for Organizers CodeForces - 418D (贪心,直径)
热门文章
- JavaSE--【JAVA】unicode为12288字符
- Notification通知在OPPO手机上不弹出提示?
- [Python]安装和运行flask框架
- CodeForces 993A Two Squares(数学 几何)
- [原]调试实战——使用windbg调试崩溃在ComFriendlyWaitMtaThreadProc
- SpringMVC访问出错No converter found for return value of type
- Downton Abbey
- DNA methylation|Transcription factors|PTM|Chromosome conformation|表观遗传学测序技术
- poj-3661 Running(DP)
- Cantor表(模拟)