POJ-2082-Terrible Sets-白红宇

POJ-2082-Terrible Sets

阅读量：7223 次

发布时间：2019-06-29

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

链接：https://vjudge.net/problem/POJ-2082#author=0

题意：

挨个给n个矩形的宽和高，求内部矩形的最大面积

思路：

单调栈，每次tmp记录出栈的总宽度。记录到下一次出栈要增加的宽度。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               using namespace std;typedef long long LL;const int MAXN = 5e4 + 10;struct Squere{ int _w; int _h;}squ[MAXN];int main(){ int n; while (scanf("%d", &n)) { if (n == -1) break; for (int i = 1;i <= n;i++) scanf("%d%d", &squ[i]._w, &squ[i]._h); stack
               
                 r; int res = 0; for (int i = 1;i <= n;i++) { int tmp = 0; while (!r.empty() && r.top()._h > squ[i]._h) { Squere f = r.top(); r.pop(); res = max(res, f._h * (f._w + tmp)); squ[i]._w += f._w; tmp += f._w; } r.push(squ[i]); } while (!r.empty()) { Squere f = r.top(); r.pop(); res = max(res, f._h * f._w); if (!r.empty()) r.top()._w += f._w; } printf("%d\n", res); } return 0;}