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

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

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

记录动态规划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;
	}
}



	

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号