hdu 1507 Largest Rectangle in a Histogram 动态规划计算最大面积
2024-08-26 05:02:20
记录动态规划dpl,dpr,分辨记录i左面的比i大的,右面比i大的,然后(dpr[i]-dpl[i]+1)*h[i]得出长度
动态转移方程while(temp>1 && h[temp-1]>=h[i]) temp=dpl[temp-1]
/*************************************************************************
> File Name: hdu1506.cpp
> Author: yang
> Mail:826123027@qq.com
> Created Time: 2014年08月24日 星期日 23:41:16
************************************************************************/ #include<iostream>
#include<stdio.h>
#include<memory.h>
using namespace std;
#define N 100005
int main(){
int dpl[N],dpr[N];
long long h[N];
int n;
while(scanf("%d",&n),n){
for(int i=1;i<=n;i++)
scanf("%lld",&h[i]);
dpl[1]=1;
int temp;
for(int i=2;i<=n;i++){
temp=i;
while(temp>1 && h[temp-1]>=h[i]) temp=dpl[temp-1];
dpl[i]=temp;
}
dpr[n]=n;
for(int i=n-1;i>=1;i--){
temp=i;
while(temp<n && h[i]<=h[temp+1]) temp=dpr[temp+1];
dpr[i]=temp;
}
long long sum,ans=0;
for(int i=1;i<=n;i++){
// cout<<dpl[i]<<" "<<dpr[i]<<endl; sum=(dpr[i]-dpl[i]+1)*h[i];
// cout<<"sum:"<<sum<<endl;
if(sum>ans) ans=sum;
}
cout<<ans<<endl;
}
}
最新文章
- 假装这些是MyEclipse的快捷键(1)
- 黄聪:手机移动端建站Jquery+CSS3+HTML5触屏滑动特效插件、实现触屏焦点图、图片轮展图
- 李洪强iOS开发之图片拉伸技巧
- kindeditor-4.1.10在线编辑器的使用[多个]
- Sicily1059-Exocenter of a Trian
- MyEclipse安装Eclipse Memory Analyzer插件,并进行错误文件分析流程
- HTML a标签 target属性作用
- EntityFramework Core不得不注意的性能优化意外收获,你会用错?
- ArcGIS API for JavaScript 4.2学习笔记[27] 网络分析之最短路径分析【RouteTask类】
- hdu1512 Monkey King(左偏树 + 并查集)
- PAT 甲级真题题解(1-62)
- C# - 设计模式目录
- 颜色空间之CIE2000色差公式
- Educational Codeforces Round 55 (Rated for Div. 2) B. Vova and Trophies
- java生产环境增量发版陷阱【原】
- linux查看操作系统的版本
- 牛客网 PAT 算法历年真题 1011 : 个位数统计 (15)
- [转]Serializable接口与Externalizable接口区别
- python 内置函数(一),低阶内置函数功能汇总
- MySQL Gap Lock问题