POSJ - 2559 - Histogram - 단조 로 운 창고 에서 가장 큰 사각형

소박 한 방법 은 모든 i 의 높이 를 매 거 하 는 것 이다. 사각형 의 폭 을 위해 양쪽 으로 가장 긴 사각형 을 찾 을 수 있 습 니 다. 모든 답 을 비교 해서 가장 큰 ans 를 얻 었 습 니 다.
물론 이렇게 하면 시간 을 초과 할 수 있다.최적화 할 수 있 는 곳 은 n 번 의 매 거 에서 여러 번 생략 할 수 있 고 단조 로 운 스 택 의 사상 을 사용 하면 불필요 한 많은 역 사 를 절약 할 수 있다.204 ms 까지 시간 을 절약 합 니 다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
__int64 max (__int64 a,__int64 b)
{return a=tt.h)
	{
		tm[top-1].r=tm[top].r;
		tt.l=tm[top].l;
		node t=tm[top];
		
		ans=max(ans,t.h*(t.r-t.l+1));
		top--;

	} 
	tm[++top]=tt;
}

int main()
{ 

	
	__int64 n,i;
	while(scanf("%I64d",&n)!=EOF)
	{
		if (!n) break;
		ans=top=0;
		node tt;
		for (i=1;i<=n;i++)
		{
			scanf("%I64d",&tt.h);
			tt.l=tt.r=i;
			insert(tt);
		}

		while(top)
		{
		 
		tm[top-1].r=tm[top].r; 
		node t=tm[top]; 
		ans=max(ans,t.h*(t.r-t.l+1));
		top--;
		}
		
		
		
		printf("%I64d
",ans);
		
	}
		
		return 0;
		
	}

POSJ - 2559 - Histogram - 단조 로 운 창고 에서 가장 큰 사각형

좋은 웹페이지 즐겨찾기