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

顾z

2018-08-20 21:01:17

Solution

**广告** [安利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)