Poj 2082 Terrible Sets-白红宇

Poj 2082 Terrible Sets

阅读量：5116 次

发布时间：2019-06-13

本文共 1979 字，大约阅读时间需要 6 分钟。

Terrible Sets

Time Limit: 1000MS Memory Limit: 30000K

Total Submissions: 5466 Accepted: 2792

Description

Let N be the set of all natural numbers {0 , 1 , 2 , . . . }, and R be the set of all real numbers. wi, hi for i = 1 . . . n are some elements in N, and w0 = 0.

Define set B = {< x, y > | x, y ∈ R and there exists an index i > 0 such that 0 <= y <= hi ,∑0<=j<=i-1wj <= x <= ∑0<=j<=iwj}

Again, define set S = {A| A = WH for some W , H ∈ R+ and there exists x0, y0 in N such that the set T = { < x , y > | x, y ∈ R and x0 <= x <= x0 +W and y0 <= y <= y0 + H} is contained in set B}.

Your mission now. What is Max(S)?

Wow, it looks like a terrible problem. Problems that appear to be terrible are sometimes actually easy.

But for this one, believe me, it's difficult.

Input

The input consists of several test cases. For each case, n is given in a single line, and then followed by n lines, each containing wi and hi separated by a single space. The last line of the input is an single integer -1, indicating the end of input. You may assume that 1 <= n <= 50000 and w1h1+w2h2+...+wnhn < 109.

Output

Simply output Max(S) in a single line for each case.

Sample Input

1 2

3 4

1 2

3 4

1 2

3 4

-1

Sample Output

题意，找面积最大的矩形，手滑一下点到讨论区，然后就开心的使用单调栈的模版。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #define maxn 100000#define maxm 10000005#define MAXN 100005#define MAXM 10005#define mem(a,b) memset(a,b,sizeof(a))#define ll long long#define inf 0x3f3f3f3fusing namespace std;int h[maxn+10];int l[maxn+10],r[maxn+10];int st[maxn+10];int sum[maxn+10];int n;void solve(){ int t=0; for(int i=0;i
              
               0&&h[st[t-1]]>=h[i]) t--; l[i]=t==0?0:(st[t-1]+1); st[t++]=i; } t=0; for(int i=n-1;i>=0;i--){ while(t>0&&h[st[t-1]]>=h[i]) t--; r[i]=t==0?n:st[t-1]; st[t++]=i; } ll res=0; for(int i=0;i

转载于:https://www.cnblogs.com/da-mei/p/9053220.html

你可能感兴趣的文章