POJ 3494 Largest Submatrix of All 1’s
2024-08-28 13:39:45
HDU 1506 Largest Rectangle in a Histogram
和这两题一样的方法。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; const int maxn=+;
int a[maxn];
int L[maxn],R[maxn];
int m,n;
int tmp[maxn][maxn],b[maxn][maxn]; void f()
{
for(int i=; i<=n; i++) L[i]=i;
for(int i=; i<=n; i++)
{
if(a[i]>a[i-]) continue;
int pre=L[i-];
while()
{
L[i]=pre;
if(pre==||a[pre-]<a[i]) break;
pre=L[pre-];
}
} for(int i=n; i>=; i--) R[i]=i;
for(int i=n-; i>=; i--)
{
if(a[i]>a[i+]) continue;
int pre=R[i+];
while()
{
R[i]=pre;
if(pre==n||a[pre+]<a[i]) break;
pre=R[pre+];
}
} } int main()
{
while(~scanf("%d%d",&n,&m))
{
memset(b,,sizeof b);
for(int i=; i<=n; i++)
for(int j=; j<=m; j++) scanf("%d",&tmp[i][j]); for(int i=; i<=n; i++)
for(int j=; j<=m; j++)
{
if(tmp[i][j]==) continue;
b[i][j]=b[i][j-]+tmp[i][j];
} int ans=;
for(int j=;j<=m;j++)
{
for(int i=;i<=n;i++) a[i]=b[i][j];
f();
for(int i=;i<=n;i++) ans=max(ans,a[i]*(R[i]-L[i]+));
}
printf("%d\n",ans);
}
return ;
}
最新文章
- Install NukeX v7.0v6 in CentOS 7
- class DelegatingFilterProxy
- c++中string类的详解
- OC4_可变数组
- Java GC 专家系列3:GC调优实践
- 高性能Java解析器实现过程详解
- Linux进程间通信——使用流套接字
- log4j:ERROR Could not find value for key log4j.appender.error
- F# 之旅(下)
- asp.net mvc 防止重复提交
- swipe.js实现支持手拔与自动切换的图片轮播
- Excel文件上传,高亮错误的行和列
- Laravel 学习笔记
- 爬虫学习笔记-urllib库
- jquery.jtable的事件
- bash中 2>;&;1 &; 的解释
- (转)JAVA常见面试题之Forward和Redirect的区别
- C#阿里云 移动推送 接入
- Oracle 11G 单机asm安装
- Radius 中 与Response Authernticator 与 Message-Authenticator的计算