【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
【BZOJ-1113】海报PLA 单调栈

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",&n);

    for (int i=; i<=n; i++) scanf("%d%d",&a,&L[i]);

    for (int i=; i<=n+; i++)

        {

            while (top && stack[top]>=L[i]) {if(stack[top]!=L[i])ans++;top--;}

            stack[++top]=L[i];

        }

    printf("%d\n",ans);

    return ;

}

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

秒客网