【BZOJ-1113】海报PLA 单调栈

1113: [Poi2008]海报PLA

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 896 Solved: 573
[Submit][Status][Discuss]

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

HINT

Source

Solution

裸题..直接上..

话说不明白既然要覆盖宽不管高,输入高有什么用...

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 250010
int n,a,ans,L[maxn],stack[maxn],top;
int main()
{
    scanf("%d
",&n);
    for (int i=1; i<=n; i++) scanf("%d%d",&a,&L[i]);
    for (int i=1; i<=n+1; i++)
        {
            while (top && stack[top]>=L[i]) {if(stack[top]!=L[i])ans++;top--;}
            stack[++top]=L[i];
        }
    printf("%d
",ans);
    return 0;
}

没好好读题,WA了一次..