51nod1158 最大子矩形 单调栈应用
2024-10-12 17:54:46
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int mp[][6],m,n,ans;
void work(int i){//以第i行为底的矩阵
int stk[6],w[]={},h[]={},top=;//高度栈,左宽栈
memset(stk,-,sizeof stk);
for(int j=;j<=m;j++)h[j]=mp[i][j];
for(int j=;j<=m;j++){
if(h[j]>stk[top])
stk[++top]=h[j],w[top]=;
else {
int cnt=;
while(top>= && stk[top]>=h[j]){
ans=max(ans,stk[top]*(w[top]+cnt));
cnt+=w[top--];
}
stk[++top]=h[j];
w[top]=cnt+;
}
}
}
int main(){
while(scanf("%d%d",&n,&m)==){
memset(mp,,sizeof mp);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&mp[i][j]); m++;//在最右边添一个全0列
for(int j=;j<=m;j++)
for(int i=;i<=n;i++)
if(mp[i][j]==)mp[i][j]=mp[i-][j]+; ans=;
for(int i=;i<=n;i++)
work(i);
printf("%d\n",ans);
}
}
最新文章
- 使用Hexo搭建专属Blog
- java多线程--几个多线程面试题小结
- 常见寻找OEP脱壳的方法
- [转]Spring 注解总结
- 预防 Session 劫持与 Session 固定攻击
- SweetAlert2 使用教程
- C#学习笔记(补充)——扩展方法、事件
- VS调试Libevent流程
- Understanding Design And Development Job Titles--reference
- Ubuntu16.04下编译vim with python support失败的原因
- Servlet的学习之Response响应对象(3)
- PAT1003
- 刨根究底字符编码之五——简体汉字编码方案(GB2312、GBK、GB18030、GB13000)以及全角、半角、CJK
- Learn c language the one day
- linux虚拟机ip地址更改
- Java进阶(二十四)Java List集合add与set方法原理简介
- [dotnet core]落地微服务特色的DevOps管道,持续集成/部署到kubernetes。
- MATLAB 显示输出数据的三种方式
- gym 101081 E. Polish Fortress 几何
- 几个PHP读取整个文件的函数readfile()、fpassthru()和file()
热门文章
- D - Stone Division HackerRank - stone-division (博弈+搜索)
- Tip:什么是JavaBean
- AtomicLong和LongAdder的区别
- MySql cmd下的学习笔记 —— 引擎和事务(engine,transaction)
- 关于链表所有操作,面试必考C++
- P1456 Monkey King
- XAF 框架中,自定义参数动作(Action),输入参数的控件可定义,用于选择组织及项目
- windows系统下简单nodejs安装及环境配置
- python用WMI模块获取系统命名空间
- EF Codefirst入门之创建数据库