!HDU 1506 Largest Rectangle in a Histogram-dp | 단일 큐 - (시간 복잡성 감소)

제목: 너비가 같고 높이가 다른 장방체가 서로 붙어 있어서 구성할 수 있는 면적이 가장 큰 장방체를 구한다
분석: 사고의 전환이기도 하다.이 문제의 주된 사고방식은 dp가 아니라 dp는 단지 보조 작용을 할 뿐이다.구체적인 방법: 각 장방체를 매거하여 이 장방체의 높이를 높이는 가장 큰 장방체 면적을 구하고 끊임없이 답을 갱신한다.l[i]와 r[i]의 수조로 i번째 직사각형의 좌우가 그것보다 높은 먼 위치를 표시하기 때문에 면적 s=a[i]*(r[i]-l[i]+1).그러나 직접적인 이중 순환은 시간을 초과할 수 있다. 이때 약간의 dp 사상을 사용했다. 여기서 사용하는 것은 dp가 점차적으로 추진하는 사상이 아니라 dp가 중간 결과를 보존하여 시간의 복잡도를 낮추는 사상이다.이중 순환이기도 하지만 dp[]의 관계로 인해 중복된 비교 절차를 많이 건너뛰었다.
이 문제의 주된 사고방식과 dp의 용법을 축적하는 데 주의해라.
내가 요 며칠 동안 단조로운 대열을 배웠을 때 이 문제도 단조로운 대열로 할 수 있다는 것을 발견했다. 매우 간단하다. 하나의 단증대열은 0~n-1의 네모난 블록의 높이를 순서대로 대열에 옮겨 넣었다. 새로 추가된 원소 A는 바로 그것에 의해 대열에서 나온 원소 B의 가장 먼 것이 B의 네모난 블록 오른쪽보다 높고 r[B]=A-1이다.왼쪽 경계는 같은 이치다.O(n)면 돼.r[i]=n-1, L[i]=0을 초기화하는 것을 주의하세요. 원소의 L[], r[] 값은 이 원소가 강제로 줄을 나갈 때 업데이트됩니다. 일부 원소의 좌우 경계는 0, n-1이기 때문에 줄을 나가지 않습니다. 스스로 설정하지 않으면 대기열을 유지할 때 업데이트하지 않고 오류가 발생합니다.
dp 코드:

#include
#include
using namespace std;
long long n,a[100005];
long long mx,sum;
int l[100005],r[100005];
long long max(long long i,long long j)
{
	return i>j?i:j;
}
void DP()
{
	mx=0;
	for(int i=0;i0&&a[t-1]>=a[i])
		   t=l[t-1];
		l[i]=t;
	}
	for(int i=n-2;i>=0;i--){
		int t=i;
		while(t>n){
		if(!n) break;
		for(int i=0;i>a[i];
		DP();
		cout<

단일 큐 코드:

#include
#define max(a,b) a>b?a:b
using namespace std;
int n;
long long a[100010],q[100010],ans;
int l[100010],r[100010];
int main()
{
	while(cin>>n){
		if(!n) break;
		int head=0,rear=-1;
		ans=-1;
		for(int i=0;i>a[i];
		for(int i=0;ia[i]){
				r[q[rear]]=i-1;
		        rear--;
			}			  
	        q[++rear]=i;
		}
		head=0,rear=-1;
		for(int i=n-1;i>=0;i--){
			while(head<=rear&&a[q[rear]]>a[i]){
				l[q[rear--]]=i+1;
			}
			q[++rear]=i;
		}
		for(int i=0;i