poj 2559 DP

兩種解法。

我想到的是最大的矩形，中間一定有個最矮的某個單位矩形，所以用兩個數組記錄histogram[i]左右兩邊第一個比它小的單位矩形的序號leftLowerId[i]和rightLowerId[i]，那麼對於histogram[i]，它自己的最大矩形面積就是(rightLowerId[i] - leftLowerId[i] - 1) * histogram[i]。

這裡找leftLowerId和rightLowerId的時候用DP加速。以rightLowerId為例，找到右邊比histogram[i]矮的矩形，停止，遇到比histogram[i]高的矩形j，直接跳到比histogram[j]矮的矩形rightLowerId[j].

#include
using namespace std;


//the histogram stored from left to right
long histogram[100001];
int rightLowerId[100001];
int leftLowerId[100001];


//from right to left
void FindRightSideLowerRec(int n)
{
	rightLowerId[n - 1] = n; // there is no rectangle on its right
	for (int i = n - 2; i >= 0; i--){

		int cid = i + 1;
		while (histogram[cid] >= histogram[i] && cid < n){
			cid = rightLowerId[cid]; // the key
		}

		rightLowerId[i] = cid;
	}
}

//from left to right
void FindLeftSideLowerRec(int n)
{
	leftLowerId[0] = -1; // there is no rectangle on its left
	for (int i = 1; i < n; i++){

		int cid = i - 1;
		while (histogram[cid] >= histogram[i] && cid > -1){
			cid = leftLowerId[cid]; // the key
		}

		leftLowerId[i] = cid;
	}
}

long long CalLargestRectangle(int n)
{
	long long largestArea = 0;

	for (int i = 0; i < n; i++)
	{
		long long width = rightLowerId[i] - leftLowerId[i] - 1;
		long long height = histogram[i];

		long long area = width * height;

		if (area > largestArea)
			largestArea = area;
	}

	return largestArea;
}

int main()
{
	int n;
	while (scanf("%d", &n)){
		if (n == 0)
			return 0;

		for (int i = 0; i < n; i++)
		{
			scanf("%d", &histogram[i]);
		}

		FindRightSideLowerRec(n); 
		FindLeftSideLowerRec(n);
		long long larea = CalLargestRectangle(n);

		printf("%I64d\n", larea);

	}
}