BZOJ 1113 [Poi2008]海報PLA 單調棧

Description

N個矩形,排成一排. 現在希望用盡量少的矩形海報Cover住它們.

Input

第一行給出數字N,代表有N個矩形.N在[1,250000] 下面N行,每行給出矩形的長與寬.其值在[1,1000000000]2 1/2 Postering

Output

最少數量的海報數.

Sample Input

5

1 2

1 3

2 2

2 5

1 4

Sample Output

4

HINT

單調棧水題。。

兩個高度一緻且中間比它們高的海報對才可以減少答案。

這樣的話用一個單調棧即可。

當然此題還有不停找區間最高值，分治解決的方法。

#include<bits/stdc++.h>
using namespace std;
int n,stk[250001];
int main(){
    scanf("%d",&n);
    int x,top=0,ans=0;
    for(int i=1;i<=n;i++){
       scanf("%d%d",&x,&x);
       while(x<=stk[top])
           if(x==stk[top--])ans++;
       stk[++top]=x;
    }
    printf("%d",n-ans);
    return 0;
}