最大子图形问题详解.doc

最大子图形问题详解宋壬初最大子图形问题包括最大子正方形、最大子矩形、最大子三角形、最大子菱形等。这些问题可以用动态规划来解决。通过最大子图形问题，我们充分掌握了动态规划的核心思想，即同一的子问题只算一次。同时培养了对于图形的敏锐的观察力。子问题1：连续的1给定一个01串，求其中最长的连续1子串的长度。比如，对于串00101110110，最长连续1子串的长度是3。它由第5到7个字符组成。怎么解决呢？我们用一个数组a1.n来记录这个01串，然后，我们用一个数组f0.n来记录子问题的结果。我们定义fi为以第i个字符结尾的连续1子串的长度。假设我们已经求出了fi-1。那么，如果ai=1，fi=fi-1+1，否则fi=0。初始的f0=0。最后，我们扫描f数组，找到最大的值就是答案。扩展：假如我们给出的是一个01矩阵，那么我们的a数组将变成2维，而其转移方式是没有变化的。不过，这次我们不仅考虑横向的连续1，还考虑纵向的。所以需要两个数组：row0.n,0.n和col0.n.0.n。那么，转移方式如下：rowi,j-1+1 (ai,j=1)rowi,j= 0 (ai,j=0)coli-1,j+1 (ai,j=1)coli,j=0 (ai,j=0)上面的连续的1是同行或同列的。那么，你能想到对角线方向连续的1的长度怎么求么？子问题2：最大子正方形给定一个01矩阵，求其中最大的一个子正方形，要求这个正方形全部由0组成。首先，我们用上面的方法，求出每个点向左扩展的连续0的长度，向上扩展的连续0的长度。不妨依然用row和col两个数组表示。通过观察，我们找出图形之间的继承关系。如果以(i-1,j-1)点为右下角的最大子正方形的边长是dpi-1,j-1，那么以(i,j)为右下角的最大子正方形的边长不会超过dpi-1,j-1+1。此外，它还受到rowi,j和coli,j的限制，不会超过这两个数。由于正方形的图形性质，以上三个限制条件是显然的。dpi-1,j-1+1dpi,j= min rowi,j coli,j经典题目：USACO 5.3.4 Big Barn子问题3：最大子1*2矩形给定一个01矩阵，求其中最大的1*2长方形，要求这个长方形只能包括0。求长方形的尺寸（我们规定高为其尺寸）。首先，我们用上面的方法，求出row数组和col数组。我们用dpi,j表示以（i，j）为左下角的最大子1*2矩形的高。那么，我们发现，其继承关系为：dpi-1,j-2+1dpi,j= min rowi,j div 2 coli,j-1 coli,j经典题目：刘思壮18岁生日模拟赛 雪地留名子问题4：最大子p*q矩形(p,q互质)给定一个01矩阵，求其中最大的p*q长方形，要求这个长方形只能包括0。求长方形的尺寸（我们规定高除以p为其尺寸）。类似上面的转移。但是，这次我们需要更多的继承关系，具体为：dpi-p,j-q+1rowi-p+1,j div qrowi-p+2,j div qdpi,j= min rowi,j div q coli,j-q+1 div p coli,j-q+2 div p coli,j div p子问题5：最面积大子矩形*这个很重要！给定一个01矩阵，求其中面积最大的全零矩形的面积。这个问题有两种解法，请参见NOI2003集训队员王知昆冬令营论文浅谈用极大化思想解决最大子矩形问题悬线法解决最大子矩形问题是一个很难的问题，大家一定要掌握。经典题目：USACO 6.1.2 Rectbarn Vijos1255 月饼盒子问题6：最大子三角形给定一个01矩阵，找出其中最大的全零等腰直角三角形。由于三角形的形状可能不同，我们一一讲解。为了简便，我们用从当前点经过直角顶点到另一个45度角点的路径来定义三角形形状。6.1 上左 三角形我们用coli,j表示从当前点向上连续1的个数，dpi,j表示以（i，j）为右下角顶点的 上左 三角形的直角边长。 dpi-1,j-1+1dpi，j=min coli,j6.2 上右 三角形 dpi-1,j+1+1dpi，j=min coli,j6.3 下左 三角形这次我们在计算col数组时，i循环倒着来。这样，我们算出的coli,j表示从一个点向下连续1的个数。 dpi+1,j-1+1dpi，j=min coli,j6.4 下右 三角形 dpi+1,j+1+1dpi，j=min coli,j6.5 左上左下 三角形我们开tmp0.n,0.n数组，tmpi,j表示以（i，j）为右下角的主对角方向连续0的个数。那么，tmpi，j=tmpi-1，j-1+1(ai，j=1) or 0 (ai，j=0)转移方程为： dpi,j-1+1dpi,j= min tmpi,j其他的方向的三角形类似，这里就不一一列举了。子问题7：最大子菱形给定一个01矩阵，求其中最大的全零菱形的边长。我们用tmp1i,j表示以（i,j）为右下角的主对角方向连续0的长度，用tmp2i,j表示以（i,j）为左下角的副对角方向连续0的长度。dpi,j为以（i,j）为下顶点的最大菱形边长。那么，我们可得到以下转移方程： dpi-1,j+1dpi,j= min dpi-2,j+1 tmp1i,j tmp2i,j观察图形，红色的表示连个对角线方向的连续的长度。蓝色和绿色表示规模小一的菱形，黄色和绿色同样表示规模小一的菱形。绿色部分是两个菱形的相交部分。可见，菱形的继承比较复杂。子问题8：其他其他的图形如果满足继承性质，也可以通过以上方式计算。这里无法一一列举，同学们可以自己进行研究。子问题9：综合题综合利用各种子图形的性质进行解题。例1：NOI2009重庆省选 红十字大意：给定一个01矩阵，让求最大的子图形，由中间的1组成的十字和四个0组成的正方形组成。求最大的红十字的大小。请点击这里查看该题的标准程序。例2：2005 全国信息学分区联赛模拟赛 创意吃鱼法例3：TSOI模拟赛之童年的记忆 小船弯弯请点击这里进入例4：TYVJ元旦模拟赛 太极图案请点击这里进入例5：TSOI第三次模拟赛 死亡陷阱例6：APIO2009第一题 采油区域解法：对于不同种类的图形分别计算，然后用这些局部最