洛谷1169 [ZJOI2007] 棋盘制作
2024-10-20 05:38:27
题意概述:给出由0 1构成的矩阵,求没有0 1 相邻的最大子矩阵的最大子正方形。
解题思路:设f[i][j]表示i j向上能到哪,l[i][j] r[i][j]表示向左/右,转移时分开计算矩形和正方形即可。
#include<cstring>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{
register int X=;register char ch=;bool flag=;
for(;!isdigit(ch);ch=getchar()) if(ch=='-') flag=;
for(;isdigit(ch);ch=getchar()) X=(X<<)+(X<<)+ch-'';
return (flag ? -X : X);
}
inline void write(int x)
{
if(x>) write(x/);
putchar(x%+'');
}
const int N=;
int l[N][N],r[N][N],f[N][N],n,m,a[N][N],ans1=,ans2=;
int min(const int x,const int y){return (x < y ? x : y);}
int max(const int x,const int y){return (x < y ? y : x);}
int main()
{
n=read(),m=read();
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
a[i][j]=read(),l[i][j]=r[i][j]=(j== ? : j),f[i][j]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
if(a[i][j] != a[i][j-])
l[i][j]=l[i][j-];
for(int j=m-;j>=;j--)
if(a[i][j] != a[i][j+])
r[i][j]=r[i][j+];
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(i > && a[i][j] != a[i-][j])
l[i][j]=max(l[i][j],l[i-][j]),r[i][j]=min(r[i][j],r[i-][j]),f[i][j]=f[i-][j]+;
int k=r[i][j]-l[i][j]+,h=min(k,f[i][j]);
ans1=max(ans1,k*f[i][j]);
ans2=max(ans2,h*h);
}
write(ans2),putchar('\n'),write(ans1);
}
最新文章
- 项目开发之UML之初识
- hdu Virtual Friends
- android的 makefile里 的常用 宏定义
- 怎么给OCR文字识别软件设置正确的扫描分辨率
- .NET Framework4.0 下的多线程
- POJ -3050 Hopscotch
- HDOJ 1237题 简单计算器
- poj2287
- C# 2 闰年平年 老狼几点了
- Vmware linux 安装 Vmware Tools 提示只读
- Android Annotations Eclipse 配置 (3)
- PHP Switch 语句
- 关于win7+VS2017环境下的opencv-contirb配置的一个坑
- 在 Activity 中实现 getContentView 操作
- Centos 04 基础系统优化命令
- BZOJ4972 八月月赛 Problem B 小Q的方格纸 二维前缀和
- 安装ik分词器以及版本和ES版本的兼容性
- 吴裕雄 python 机器学习-KNN算法(1)
- 2.select查询用法
- Spring学习13-中IOC(工厂模式)和AOP(代理模式)的详细解释