[bzoj1113]海报

2024-10-19 15:33:30

ans肯定不会超过n，因为我们可以每一列都放一个矩阵
考虑减小答案，肯定是要放横的，也就是让两个高度一样的矩阵同时被消除掉，那么中间不能存在比他们低的矩阵
问题即判断一个点之前第一个小于等于它的点是不是等于他（等于就ans-1），然后用单调栈维护之前的递减即可

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int n,ans,a[300005],s[300005];

 4 int main(){

 5     scanf("%d",&n);

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

 7     for(int i=1;i<=n+1;i++){

 8         while ((s[0])&&(s[s[0]]>=a[i]))

 9             if (s[s[0]--]==a[i])ans++;

10         s[++s[0]]=a[i];

11     }

12     printf("%d",n-ans);

13 }

最新文章

热门文章