BZOJ1113 海报PLA

好像是很古老的题？现在BZOJ上找不到该题，所以没有提交。

1113: [Poi2008]海报PLA

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 810 Solved: 507
[Submit][Status][Discuss]

Description

N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.

（SilverN附注：矩形外不能贴海报）

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
BZOJ1113 海报PLA

Sample Output

根据神秘提示可以用单调栈来处理。

先假设每个矩形都用一张海报覆盖。从左到右遍历，对于一个矩形，如果左边有和它高度相等的矩形（且两个矩形之间没有更低的），那么可以用一大张海报覆盖这两个矩形和它们之间的部分（见上图），则总海报数-- 。

用单调栈维护“左边第一个比当前矩形低的矩形”，如果该矩形高度和当前矩形相同，那么总海报数--

代码如下：

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 using namespace std;

 int n;

 int st[];

 int t=;

 int ans;

 int main(){

     scanf("%d",&n);

     ans=n;//最差情况需要n张海报

     int i,j;

     int x,y;

     scanf("%d%d",&x,&y);

     st[++t]=y;

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

         scanf("%d%d",&x,&y);

         while(t> && st[t]>y)t--;

         if(st[t]==y)ans--;

         st[++t]=y;

     }

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

     return ;

 }

秒客网