首页 > 代码库 > 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的最大子矩阵
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。