POJ 2082 - Terrible Sets

http://poj.org/problem?id=2082

概要

数列 w[i], h[i] を i = 1, ..., n に対して

w_i, h_i \in \mathbb{N}

w_0 = 0

とし，さらに

B = \left{<x, y> \mid x, y \in \mathbb{N}, \exists i > 0, 0 \le y \le h_i, \bigsum_{j = 0}^{i-1}w_i \le x \le \bigsum_{j = 0}^{i} w_j \right}

S=\left{A\mid W, H \in \mathbb{R}^+, A = WH \wedge \exists x_0, y_0 \in \mathbb{N} \mbox{such that} \left{ <x, y>\mid x_0 \le x \le x_0+W \wedge y_0 \le y \le y_0+H \right} \subseteq B \right}

と B, S を定義したときの S の最大値を答える．

制約

解法

よく読むと，B は二次元上に 幅 w[i] で高さ h[i] の長方形を地面の上に左から並べていったときの全体の領域を表していて，S はその中に作れる，辺が軸に平行な任意の長方形の面積を表している．

例えばサンプルはそれぞれ図のような 3 つの長方形を表していて，答えは色が塗られた領域の面積である．

2082-1.svg 2082-2.svg

 1 #include <cstdio>
 2 #include <stack>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   while (scanf("%d", &N) != EOF && N != -1) {
 9     stack<pair<int,int> > stk;
10     int prev_h = -1;
11     int ans = 0;
12     for (int i = 0; i < N; i++) {
13       int w, h;
14       scanf("%d %d", &w, &h);
15       if (h >= prev_h) {
16         stk.push(make_pair(w, h));
17       } else {
18         int width = 0;
19         while (!stk.empty() && stk.top().second > h) {
20           width += stk.top().first;
21           ans = max(ans, width * stk.top().second);
22           stk.pop();
23         }
24         width += w;
25         stk.push(make_pair(width, h));
26       }
27       prev_h = h;
28     }
29 
30     for (int width = 0; !stk.empty(); stk.pop()) {
31       width += stk.top().first;
32       ans = max(ans, width * stk.top().second);
33     }
34     printf("%d\n", ans);
35   }
36   return 0;
37 }
poj/2082.cc