HihoCoder1664 01间隔方阵([Offer收割]编程练习赛40)(DP)
2024-09-04 12:40:56
给定一个NxM的01矩阵,小Hi希望从中找到一个01间隔的子方阵,并且方阵的边长越大越好。
例如对于
0100100
1000101
0101010
1010101
0101010
在右下角有一个4x4的01间隔方阵。
Input
第一行包含两个整数N和M。
以下N行M列包含一个NxM的01矩阵。
对于30%的数据,1 ≤ N, M ≤ 250
对于100%的数据,1 ≤ N, M ≤ 1000
Output
输出最大的01间隔方阵的边长。
Sample Input
5 7
0100100
1000101
0101010
1010101
0101010
Sample Output
4
面积DP。
加强版:hihocoder1673
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=;
char c[maxn][maxn];
int L[maxn][maxn],H[maxn][maxn];
int a[maxn][maxn];
int main()
{
int n,m,i,j,ans=;
scanf("%d%d",&n,&m);
for(i=;i<=n;i++) scanf("%s",c[i]+);
for(i=;i<=n;i++) L[i][]=;
for(i=;i<=m;i++) H[][i]=;
for(i=;i<=n;i++)
for(j=;j<=m;j++)
L[i][j]=c[i][j]==c[i][j-]?:L[i][j-]+; //左延伸
for(i=;i<=m;i++)
for(j=;j<=n;j++)
H[j][i]=c[j][i]==c[j-][i]?:H[j-][i]+; //上延伸
for(i=;i<=n;i++)
for(j=;j<=m;j++){
if(i==||j==||c[i][j]!=c[i-][j-])a[i][j]=; //对角线是一样的
else {
a[i][j]=min(a[i-][j-]+,L[i][j]);
a[i][j]=min(a[i][j],H[i][j]);
}
if(a[i][j]>ans) ans=a[i][j];//这一行复制过来的时候被删了。。。
}
printf("%d\n",ans);
return ;
}
最新文章
- h5上传图片及预览
- 冰冻三尺非一日之寒-mysql(orm/sqlalchemy)
- Android RecyclerView 的简单使用
- ECMAScript 5中的数据属性和访问器属性
- ExtJS要利用观察者模式 去实现自定义的事件
- git subtree有效管理公共第三方lib
- MySQL索引和优化查询
- BZOJ 1084 最大子矩阵
- zookeeper 丢失事件/miss event
- UVA315- Network(无向图割点)
- SuperSocket+unity 网络笔记
- java中的static关键字详解
- RTSP连接中断重连的问题
- ProtoBuf3 C++使用篇
- tensorflow使用多个gpu训练
- 使用InstallShield打包windriver驱动-转
- 关于div一侧固定,另一侧自适应
- IDEA配置spring
- 关于NuGet
- mysql的一些规范