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:[email protected] 
	> Created Time: 2014年08月24日 星期日 23:41:16
 ************************************************************************/

#include
#include
#include
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(tempans) ans=sum;
		}
		cout<