bzoj1113: [Poi2008]海报PLA

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #define maxn 250005
 7 using namespace std;
 8 
 9 int n,top,stack[maxn],ans;
10 
11 int main(){
12     int u,v;
13     scanf("%d",&n);
14     top=ans=0,memset(stack,0,sizeof(stack));
15     for (int i=1;i<=n;i++){
16         scanf("%d%d",&u,&v);
17         while (top&&stack[top]>v) top--;
18         stack[++top]=v;
19         if (stack[top]!=stack[top-1]) ans++;
20     }
21     printf("%d
",ans);
22     return 0;
23 }

View Code

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1113

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

做法：思路题，这题显然只与高有关，如果有两个矩阵的高相等，并且他们之间的矩阵的高都不小于他们的高，这样他们两个矩阵就只需要用一个海报来cover了。

所以我们可以用高效的单调栈来维护。