BZOJ1113: [Poi2008]海报PLA

【传送门：BZOJ1113】

---

简要题意：

　　给出n个矩阵与每个矩阵的长宽，n个矩阵按输入顺序排成一排，求出能用多少个矩阵来覆盖所有矩阵

---

题解：

　　鸽了好久博客，一直在做书。。

　　先来一道水题爽一发

　　直接用栈维护一段长度严格上升的序列，每新进一个矩阵，就判断与队头的长度大小，然后实时更新答案就可以了

---

参考代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
struct node
{
    int x,y;
}a[310000];
int sta[310000];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
    int tp=0;
    sta[++tp]=1;a[n+1].y=0;
    int ans=0;
    for(int i=2;i<=n+1;i++)
    {
        while(tp!=0&&a[sta[tp]].y>=a[i].y)
        {
            if(a[sta[tp]].y>a[i].y) ans++;
            tp--;
        }
        sta[++tp]=i;
    }
    printf("%d
",ans);
    return 0;
}