POJ-2082 : Terrible Sets

問題概要

色々書いてあるけど、要するにヒストグラムの中の最大長方形を求める問題。

解法

All nearest smaller valuesの応用。

acceptされたコード

#include <cstdio>
#include <vector>
using namespace std;

const int MAX_N = 50000;
int N;
int widths[MAX_N], hs[MAX_N];
int accum[MAX_N + 1];

int calcLargestRectangle(const vector<int>& hs) {
	const int n = hs.size();
	vector<int> stack, froms(n), tos(n);
	stack.reserve(n);
	for (int i = 0; i < n; ++i) {
		for (;!stack.empty() && hs[stack.back()] >= hs[i]; stack.pop_back()) ;
		froms[i] = (stack.empty() ? 0 : (stack.back() + 1));
		stack.push_back(i);
	}

	stack.clear();
	for (int i = n - 1 ; i >= 0; --i) {
		for (;!stack.empty() && hs[stack.back()] >= hs[i]; stack.pop_back()) ;
		tos[i] = (stack.empty() ? n : stack.back());
		stack.push_back(i);
	}

	int ans = 0;
	for (int i = 0; i < n; ++i) {
		updateMax(ans, hs[i] * (accum[tos[i]] - accum[froms[i]]));
	}

	return ans;
}

bool init() {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d%d", widths + i, hs + i);
	}
	return N >= 0;
}

int solve() {
	for (int i = 0; i < N; ++i) {
		accum[i+1] = accum[i] + widths[i];
	}
	return calcLargestRectangle(vector<int>(hs, hs+N));
}

int main() {
	for(;init();){
		printf("%d\n", solve());
	}

	return 0;
}