题解 P2701 【[USACO5.3]巨大的牛棚Big Barn】
顾z
2018-08-20 21:01:17
**广告** [安利blog](https://www.luogu.org/blog/RPdreamer/#)
**题目大意**
给定一个01棋盘,求其中全为1的最大正方形边长。
//暂且这么理解,有树的位置我们视为0.
**分析:**
发现题解没有用悬线法的 所以介绍一下
~~说实话我快写吐了~~
以下内容部分参考[@Clove_unique](https://blog.csdn.net/Clove_unique/article/details/50512624)
**悬线法**
用途:
解决给定矩阵中满足条件的最大子矩阵
做法:
用一条线(横竖貌似都行)左右移动直到不满足约束条件或者到达边界
定义几个东西:
left[i][j]:代表从(i,j)能到达的最左位置
right[i][j]:代表从(i,j)能到达的最右位置
up[i][j]:代表从(i,j)向上扩展最长长度.
这里给出递推公式:
left[i][j]=max(left[i][j],left[i-1][j]
right[i][j]=min(right[i][j],right[i-1][j]
至于为什么递推公式中考虑上一层的情况?
是因为up数组的定义,up数组代表向上扩展最长长度, 所以需要考虑上一层的情况.而我们要考虑上一层的情况的话,需要考虑左右边界问题,因此递推公式中分别取max与min即可。
然后我们去利用dp方程去求解即可.
------------------代码--------------------
```cpp
#include<bits/stdc++.h>
#define IL inline
#define RI register int
#define N 1008
IL void read(int &x){
int f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
x*=f;
}
int res[N][N],n,m,ans;
int left[N][N],right[N][N],up[N][N];
int main()
{
read(n),read(m);
for(RI i=1;i<=n;i++)
for(RI j=1;j<=n;j++)
{
left[i][j]=right[i][j]=j;
up[i][j]=1;
}//千万不要忘记初始化!!
for(RI i=1,x,y;i<=m;i++)
{
read(x),read(y);
res[x][y]=1;
}
for(RI i=1;i<=n;i++)
for(RI j=2;j<=n;j++)
if(res[i][j]==0&&res[i][j-1]==0)
left[i][j]=left[i][j-1];//预处理左边界
for(RI i=1;i<=n;i++)
for(RI j=n-1;j>0;j--)
if(res[i][j]==0&&res[i][j+1]==0)
right[i][j]=right[i][j+1];//预处理右边界
for(RI i=1;i<=n;i++)
for(RI j=1;j<=n;j++)
{
if(i>1&&res[i][j]==0&&res[i-1][j]==0)
{
left[i][j]=std::max(left[i][j],left[i-1][j]);
right[i][j]=std::min(right[i][j],right[i-1][j]);
up[i][j]=up[i-1][j]+1;
}
int a=right[i][j]-left[i][j]+1;
int b=std::min(a,up[i][j]);
ans=std::max(ans,b);
}
printf("%d",ans);
}
```
悬线法题目:[P1169 棋盘制作](https://www.luogu.org/problemnew/show/P1169) [p4147 玉蟾宫](https://www.luogu.org/problemnew/show/P4147) [p2701 巨大的牛棚](https://www.luogu.org/problemnew/show/P2701) [p1387 最大正方形](https://www.luogu.org/problemnew/show/P1387)