POJ 2796 Feel Good

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 ;
}

最新文章

  1. Install NukeX v7.0v6 in CentOS 7
  2. class DelegatingFilterProxy
  3. c++中string类的详解
  4. OC4_可变数组
  5. Java GC 专家系列3:GC调优实践
  6. 高性能Java解析器实现过程详解
  7. Linux进程间通信——使用流套接字
  8. log4j:ERROR Could not find value for key log4j.appender.error
  9. F# 之旅(下)
  10. asp.net mvc 防止重复提交
  11. swipe.js实现支持手拔与自动切换的图片轮播
  12. Excel文件上传,高亮错误的行和列
  13. Laravel 学习笔记
  14. 爬虫学习笔记-urllib库
  15. jquery.jtable的事件
  16. bash中 2&gt;&amp;1 &amp; 的解释
  17. (转)JAVA常见面试题之Forward和Redirect的区别
  18. C#阿里云 移动推送 接入
  19. Oracle 11G 单机asm安装
  20. Radius 中 与Response Authernticator 与 Message-Authenticator的计算

热门文章

  1. Inno Setup入门(二)&mdash;&mdash;修改安装过程中的图片
  2. profile和bash
  3. android--屏幕旋转方法总结
  4. HTML-中&lt;li&gt;标签value值的兼容问题
  5. struts2的工作原理
  6. php des 加密类
  7. RMQ 详解
  8. Linux 监控文件事件
  9. Json解析要点
  10. CF 299 div2 C 博弈