【POI 2008】【bzoj 1113】海报PLA（单调栈）

好久没用过单调栈了 练练手

最多贴n块海报

我们发现能省海报的情况 当且仅当有两个矩形 他们高度一样 而中间夹着的矩形都比且他们高

维护高的单调栈 每加入一个矩形 判断它左边第一个小于等于它高度的矩形的高度是否等于它的高度

#include<bits/stdc++.h>
using namespace std;
template<class T>
inline void read(T &x)
{
    x=0;
    static char ch=getchar();
    while(ch<'0'||ch>'9')   ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
} 
int n,sta[250005],top;
int main()
{
    read(n);
    int ans=n;
    for(int i=1,x,y;i<=n;i++)
    {
        read(x); read(y);
        while(top&&sta[top]>y)  top--;
        if(sta[top]==y) ans--;
        sta[++top]=y;
    }
    cout<<ans;
    return 0;
}

转载于:https://www.cnblogs.com/Patrickpwq/articles/9848115.html