前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >hdu 1507 Largest Rectangle in a Histogram 动态规划计算最大面积

hdu 1507 Largest Rectangle in a Histogram 动态规划计算最大面积

作者头像
全栈程序员站长
发布2022-07-12 17:59:54
1300
发布2022-07-12 17:59:54
举报

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

记录动态规划dpl,dpr,分辨记录i左面的比i大的,右面比i大的,然后(dpr[i]-dpl[i]+1)*h[i]得出长度

动态转移方程while(temp>1 && h[temp-1]>=h[i]) temp=dpl[temp-1]

代码语言:javascript
复制
/*************************************************************************
	> 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;
	}
}

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/118516.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021年12月,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档