题解：P2701 [USACO5.3] 巨大的牛棚Big Barn

· · 题解

题解区里好像没有单调栈的做法，这篇题解就讲解单调栈的做法。

多倍经验。

Solution

考虑先 O(n^2) 预处理每个点左边一共有多少个连续的空地。

枚举牛棚右上角点的 x 坐标，那么转化成了选择一个区间（就是确定牛棚右边那条边的位置），最大化区间内空地个数的最小值和区间长度的最小值。

转化成的这个问题就和 这题 差不多。

当空地个数最小值不变时，区间长度显然是越长越好。

考虑求出每个位置左边第一个比他空地个数小的位置和右边第一个比他小的，就能求出区间长度。

单调栈即可，时间复杂度 O(n^2)。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1001;
int n,m,ans,a[N][N];
int L[N],R[N],s[N];

int main()
{
    scanf("%d%d",&n,&m);
    while (m--) {
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=1;
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            a[i][j]=a[i][j]?0:a[i][j-1]+1;

    for (int j=1;j<=n;j++)
    {
        for (int i=1,top=0;i<=n;i++) {
            while (top&&a[s[top] ][j]>=a[i][j]) R[s[top] ]=i,top--;
            L[i]=s[top],R[i]=n+1,s[++top]=i;
        }
        for (int i=1;i<=n;i++)
        ans=max(ans,min(R[i]-L[i]-1,a[i][j]) );
    }
    printf("%d",ans);
    return 0;
}