首页 > 代码库 > 51nod1158 全是1的最大子矩阵

51nod1158 全是1的最大子矩阵

跟最大子矩阵差不多O(n3)扫一下。有更优写法?挖坑!

#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)int read(){	int x=0;char c=getchar();	while(!isdigit(c)) c=getchar();	while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();	return x;}const int nmax=505;int a[nmax][nmax];void maxs(int &a,int b){	if(a<b) a=b;}int main(){	int m=read(),n=read();	rep(i,1,n) rep(j,1,m) a[i][j]=read(),a[i][j]+=a[i-1][j];	int ans=0,cnt;	rep(i,1,n) rep(j,i,n) {		cnt=0;		rep(k,1,m){		    if(a[j][k]-a[i-1][k]!=j-i+1) maxs(ans,cnt*(j-i+1)),cnt=0;		    else cnt++;	    }	    maxs(ans,cnt*(j-i+1));	}	printf("%d\n",ans);	return 0;}

  

1158 全是1的最大子矩阵技术分享
基准时间限制:1 秒 空间限制:131072 KB 分值: 80 难度:5级算法题
技术分享 收藏
技术分享 关注
给出1个M*N的矩阵M1,里面的元素只有0或1,找出M1的一个子矩阵M2,M2中的元素只有1,并且M2的面积是最大的。输出M2的面积。
 
Input
第1行:2个数m,n中间用空格分隔(2 <= m,n <= 500)第2 - N + 1行:每行m个数,中间用空格分隔,均为0或1。
Output
输出最大全是1的子矩阵的面积。
Input示例
3 31 1 01 1 10 1 1
Output示例
4

51nod1158 全是1的最大子矩阵