hdu 1506（dp || 单调栈）

题意：这题是要找最大的矩形面积。

解题思路：这题的关键是要找每个条形能够往左和往右能够到达的最大长度。我最开始的思路是单调栈去维护，只要入栈的元素比栈顶元素小，栈顶就要出栈，并且知道其最右能够到达的最远距离。当要入栈的元素已经找到了位置，那么它左边的元素所在的位置就是其能到达的最左距离。

这道题比较坑，要用__int64位，而且在当栈为空时，加入的新元素的最左是能够到达1的，这里我开始没发现，结果WA到死。。。

这里还有一个dp版本的，感觉实际上和单调栈差不多，都是找最左和最右的距离。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 100005;
struct Node
{
	__int64 h;
	int id;
}Stack[maxn];
struct Keep
{
	__int64 l,r,h;
}res[maxn];
__int64 n,top,hi[maxn];

int main()
{
	while(scanf("%I64d",&n)!=EOF && n)
	{
		for(__int64 i = 1; i <= n; i++)
		{
			scanf("%I64d",&hi[i]);
			res[i].l = res[i].r = i;
			res[i].h = hi[i];
		}
		top = 0;
		for(__int64 i = 1; i <= n; i++)
		{
			while(top > 0 && hi[i] <= Stack[top-1].h)
			{
				res[Stack[top-1].id].r = i - 1;
				top--;
			}
			Stack[top].id = i;
			Stack[top].h = hi[i];
			if(top != 0)
				res[i].l = Stack[top-1].id + 1;
			else res[i].l = 1;	//最容易丢掉的条件,一直WA的原因
			top++;
		}
		while(top > 0)
		{
			res[Stack[top-1].id].r = n;
			top--;
		}
		__int64 ans = 0;
		for(int i = 1; i <= n; i++)
		{
			__int64 area = (res[i].r - res[i].l + 1) * res[i].h;
			if(area > ans)
				ans = area;
		}
		printf("%I64d\n",ans);
	}
	return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 100005;
int n,l[maxn],r[maxn];
__int64 hi[maxn];

int main()
{
	while(scanf("%d",&n)!=EOF && n)
	{
		for(int i = 1; i <= n; i++)
			scanf("%I64d",&hi[i]);
		l[1] = 1; r[n] = n;
		int t;
		for(int i = 2; i <= n; i++)	//更新每个l[i]
		{
			t = i;
			while(t > 1 && hi[t-1] >= hi[i]) t = l[t-1];
			l[i] = t;
		}
		for(int i = n - 1; i >= 1; i--) //更新每个r[i]
		{
			t = i;
			while(t < n && hi[t+1] >= hi[i]) t = r[t+1];
			r[i] = t;
		}
		__int64 ans = 0, tmp = 0;
		for(int i = 1; i <= n; i++)
		{
			tmp = (r[i] - l[i] + 1) * hi[i];
			if(tmp > ans)
				ans = tmp;
		}
		printf("%I64d\n",ans);
	}
	return 0;
}