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; }