poj 2082 Terrible Sets (前缀和，单调栈)
题意：这道题简直就是。。。教给大家怎么把一句话把简单的题让人出得看不懂。。。真的一点意思都没有。给出n个矩形的宽度和高度，这些矩形并排顺次排列在x轴上，问最大面积。
思路：单调栈。 之前的最大矩形面积的宽度都是1.。这次不是1.。做个宽度的前缀和就好。。。1A
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月03日 星期三 18时54分40秒
4File Name :code/poj/2082.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <stack>
14#include <set>
15#include <map>
16#include <string>
17#include <cmath>
18#include <cstdlib>
19#include <ctime>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=5E4+7;
35pi a[N];
36int l[N],r[N];
37int sum[N];
38int n;
39stack<int>stk;
40int main()
41{
42 #ifndef ONLINE_JUDGE
43 freopen("code/in.txt","r",stdin);
44 #endif
45
46 while (~scanf("%d",&n))
47 {
48 if (n==-1) break;
49 while (!stk.empty()) stk.pop();
50 sum[0] = 0 ;
51 for ( int i = 1 ; i <= n ; i++)
52 {
53 scanf("%d %d",&a[i].fst,&a[i].sec);
54 sum[i] = sum[i-1] + a[i].fst;
55 }
56
57 a[0].sec = -1;
58 a[n+1].sec = -1;
59 stk.push(0);
60 int x;
61 for ( int i = 1 ; i <= n ; i++)
62 {
63 for (x=stk.top() ; a[x].sec>=a[i].sec ; x = stk.top()) stk.pop();
64 l[i] = x+1;
65 stk.push(i);
66 }
67
68 while (!stk.empty()) stk.pop();
69 stk.push(n+1);
70 for ( int i = n ; i >=1 ; i--)
71 {
72 for (x=stk.top() ; a[x].sec>=a[i].sec ; x =stk.top()) stk.pop();
73 r[i] = x-1;
74 stk.push(i);
75 }
76 int ans = 0 ;
77 for ( int i = 1 ; i <= n ; i++) ans = max(ans,(sum[r[i]]-sum[l[i]-1])*a[i].sec);
78 printf("%d\n",ans);
79
80
81
82
83 }
84
85
86 #ifndef ONLINE_JUDGE
87 fclose(stdin);
88 #endif
89 return 0;
90}