学步园

    题目ＵＲＬ：http://acm.hdu.edu.cn/showproblem.php?pid=1506

　这是一道动态规划求解题目，如果暴力枚举起点和终点的话，以这道题目的数据量，必然超时。

　动态规划求解的两个重要函数，left[i]:表示从left[i]到i的所有的立方柱的高度都大于或等于第i个立方柱的高度。很显然，当前i-1个的leff[i]求解出来之后，left[i]的求解便很简单了，不断的往前跳跃的找就行了。

   HDOJ上不认long long类型，得用_int64这种64位的长整型。

   我的AC代码：

#include <iostream>
#include <stdio.h>
using namespace std;

const int Max = 100000 + 10;
_int64 le[Max], ri[Max], h[Max];

int main()
{
	int n;
	while(scanf("%d", &n) && n)
	{
		h[0] = h[n+1] = -1;
		for(int i(1); i<=n; ++i) scanf("%I64d", h+i);

		for(int i=1; i<=n; ++i)
		{
			le[i] = i;
			while(h[i] <= h[le[i] - 1]) le[i] = le[le[i] - 1];
		}

		for(int i=n; i>=1; --i)
		{
			ri[i] = i;
			while(h[i] <= h[ri[i] + 1]) ri[i] = ri[ri[i] + 1];
		}

		_int64 max = 0;
		for(int i=1; i<=n; ++i)
		{
			_int64 temp = (ri[i] - le[i] + 1) * h[i];
			max = max > temp ? max : temp;
		}
		printf("%I64d\n", max);
	}
	system("pause");
	return 0;
}