【悬线法】学习总结

主要用于求满足某条件的最大矩阵

定义：

一条竖线，竖线的上端点位于矩阵的上边界或是一个障碍点，然后对这条悬线进行左右移动，直到移至障碍点或者是矩阵边界，进行确定这条悬线所在的极大矩阵。
底线为(i,j)的悬线
Left[]存每个点能达到的最右位置
Right[]存放每个点能到达的最左边的位置
height[]为高度
递推公式：
height[i,j]=height[i-1,j]+1

left[i,j]=max( left[i-1,j] , (i-1,j)左边第一个障碍点位置,边界0也是障碍点 )

right[i,j]=max( right[i-1,j] , (i-1,j)右边第一个障碍点位置,边界m也是障碍点 )
对于以点(i,j)为底的悬线对应的子矩形，它的面积为(right[i,j]-left[i,j])*height[i,j]
最终的解：
Result＝max(right[i,j]-left[i,j])*height[i,j]

例题:

P1169 棋盘制作 p4147 玉蟾宫 p2701 巨大的牛棚 p1387 最大正方形