POJ2559 && POJ2082(单调栈)

POJ2559题目链接

题意:求出一些小矩形组成的图片的最大矩形面积。

思路:设所求矩形为L,枚举L的右边界,在每次枚举中再枚举L的高度。通过一个单调栈(不减)来实现。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int h[100555];
int main(){
    //freopen("a.txt", "r", stdin);
    int n;
    while(scanf("%d", &n)!=EOF && n){
        stack<int> s;
        for(int i = 1; i <=n; i++)
            scanf("%d", &h[i]);
        s.push(0);
        h[n+1] = 0;
        long long ans =0;
        for(int i = 1; i <=n+1; i++){
            while(h[i] < h[s.top()]){
                int a = h[s.top()];
                s.pop();
                int b = i-s.top()-1;
                long long tem = (long long)a*b;
                if(ans < tem)
                    ans = tem;
            }
            s.push(i);
        }
        cout << ans << endl;
    }
    return 0;
}

WA了几发的原因是,当s.top()作为所求矩形高时,所求矩形的长不是从这个矩形到i的长度,而应该是栈中前一个元素的右边的矩形到i的长度。

POJ2082题目链接

一样的题,只不过长不是1了,是给定的。

看讨论版有人说O(n^2)也能过,果断暴力了一发,然后T了,老老实实的写单调栈。。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int h[50005];
int l[50005];
int main(){
    //freopen("a.txt", "r", stdin);
    int n;
    while(scanf("%d", &n)!=EOF && n!=-1){
        int ans = 0;
        l[0] = 0;
        for(int i = 1; i <= n; i++){
            int f;
            scanf("%d%d", &f, &h[i]);
            l[i] = l[i-1]+f;
        }
        //for(int i = 1; i <= n; i++)cout << l[i] << endl;
        stack<int> s;
        s.push(0);
        h[++n] = 0;
        for(int i = 1; i <= n; i++){
            while(h[i] < h[s.top()]){
                int a = h[s.top()];
                s.pop();
                int b = l[i-1]-l[s.top()];
                int tem = a*b;
                //cout << "a:" <<a << "b:" << b <<endl;
                //cout << tem <<endl;
                if(tem > ans)
                    ans = tem;
            }
            s.push(i);
        }

        cout << ans << endl;
    }
    return 0;
}

Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with STL