最大子图形问题详解
发表时间：2010-05-04 20:09:46 浏览(4769) 评论(3)
最大子图形问题包括最大子正方形、最大子矩形、最大子三角形、最大子菱形等。这些问题可以用动态规划来解决。
通过最大子图形问题，我们充分掌握了动态规划的核心思想，即同一的子问题只算一次。同时培养了对于图形的敏锐的观察力。
子问题1：连续的1
给定一个01串，求其中最长的连续1子串的长度。
比如，对于串00101110110，最长连续1子串的长度是3。它由第5到7个字符组成。
怎么解决呢？我们用一个数组a[1..n]来记录这个01串，然后，我们用一个数组f[0..n]来记录子问题的结果。我们定义f[i]为以第i个字符结尾的连续1子串的长度。假设我们已经求出了f[i-1]。那么，如果a[i]=1，f[i]=f[i-1]+1，否则f[i]=0。初始的f[0]=0。最后，我们扫描f数组，找到最大的值就是答案。
扩展：假如我们给出的是一个01矩阵，那么我们的a数组将变成2维，而其转移方式是没有变化的。不过，这次我们不仅考虑横向的连续1，还考虑纵向的。所以需要两个数组：row[0..n,0..n]和col[0..n.0..n]。那么，转移方式如下：
row[i,j-1]+1 (a[i,j]=1)
row[i,j]=
0 (a[i,j]=0)
col[i-1,j]+1 (a[i,j]=1)
col[i,j]=
0 (a[i,j]=0)
上面的连续的1是同行或同列的。那么，你能想到对角线方向连续的1的长度怎么求么？
子问题2：最大子正方形
给定一个01矩阵，求其中最大的一个子正方形，要求这个正方形全部由0组成。
首先，我们用上面的方法，求出每个点向左扩展的连续0的长度，向上扩展的连续0的长度。不妨依然用row和col两个数组表示。
通过观察，我们找出图形之间的继承关系。如果以(i-1,j-1)点为右下角的最大子正方形的边长是dp[i-1,j-1]，那么以(i,j)为右下角的最大子正方形的边长不会超过dp[i-1,j-1]+1。此外，它还受到row[i,j]和col[i,j]的限制，不会超过这两个数。由于正方形的图形性质，以上三个限制条件是显然的。
dp[i-1,j-1]+1
dp[i,j]= min row[i,j]
col[i,j]
经典题目：USACO 5.3.4 Big Barn
子问题3：最大子1*2矩形
给定一个01矩阵，求其中最大的1*2长方形，要求这个长方形只能包括0。求长方形的尺寸（我们规定高为其尺寸）。
首先，我们用上面的方法，求出row数组和col数组。我们用dp[i,j]表示以（i，j）为左下角的最大子1*2矩形的高。那么，我们发现，其继承关系为：
dp[i-1,j-2]+1
dp[i,j]= min row[i,j] div 2
col[i,j-1]
col[i,j]
经典题目：刘思壮18岁生日模拟赛 雪地留名
子问题4：最大子p*q矩形(p,q互质)
给定一个01矩阵，求其中最大的p*q长方形，要求这个长方形只能包括0。求长方形的尺寸（我们规定高除以p为其尺寸）。
类似上面的转移。但是，这次我们需要更多的继承关系，具体为：
dp[i-p,j-q]+1
row[i-p+1,j] div q
row[i-p+2,j] div q
dp[i,j]= min ………………
row[i,j] div q
col[i,j-q+1] div p
col[i,j-q+2] div p
………………
col[i,j] div p
子问题5：最面积大子矩形
*这个很重要！
给定一个01矩阵，求其中面积最大的全零矩形的面积。
这个问题有两种解法，请参见NOI2003集训队员王知昆冬令营论文《浅谈用极大化思想解决最大子矩形问题》
悬线法解决最大子矩形问题是一个很难的问题，大家一定要掌握。
经典题目：USACO 6.1.2 Rectbarn
Vijos1255 月饼盒
子问题6：最大子三角形
给定一个01矩阵，找出其中最大的全零等腰直角三角形。由于三角形的形状可能不同，我们一一讲解。
为了简便，我们用从当前点经过直角顶点到另一个45度角点的路径来定义三角形形状。
6.1 上——左 三角形
我们用col[i,j]表示从当前点向上连续1的个数，dp[i,j]表示以（i，j）为右下角顶点的 上——左 三角形的直角边长。
dp[i-1,j-1]+1
dp[i，j]=min
col[i,j]
6.2 上——右 三角形
dp[i-1,j+1]+1
dp[i，j]=min
col[i,j]
6.3 下——左 三角形
这次我们在计算col数组时，i循环倒着来。这样，我们算出的col[i,j]表示从一个点向下连续1的个数。
dp[i+1,j-1]+1
dp[i，j]=min
col[i,j]
6.4 下——右 三角形
dp[i+1,j+1]+1
dp[i，j]=min
col[i,j]
6.5 左上——左下 三角形
我们开tmp[0..n,0..n]数组，tmp[i,j]表示以（i，j）为右下角的主对角方向连续0的个数。那么，tmp[i，j]=tmp[i-1，j-1]+1(a[i，j]=1) or 0 (a[i，j]=0)
转移方程为：
dp[i,j-1]+1
dp[i,j]= min
tmp[i,j]
其他的方向的三角形类似，这里就不一一列举了。
子问题7：最大子菱形
给定一个01矩阵，求其中最大的全零菱形的边长。
我们用tmp1[i,j]表示以（i,j）为右下角的主对角方向连续0的长度，用tmp2[i,j]表示以（i,j）为左下角的副对角方向连续0的长度。dp[i,j]为以（i,j）为下顶点的最大菱形边长。那么，我们可得到以下转移方程：
dp[i-1,j]+1
dp[i,j]= min dp[i-2,j]+1
tmp1[i,j]
tmp2[i,j]
观察图形，红色的表示连个对角线方向的连续的长度。蓝色和绿色表示规模小一的菱形，黄色和绿色同样表示规模小一的菱形。绿色部分是两个菱形的相交部分。可见，菱形的继承比较复杂。
通过最大子图形问题，我们充分掌握了动态规划的核心思想，即同一的子问题只算一次。同时培养了对于图形的敏锐的观察力。
子问题1：连续的1
给定一个01串，求其中最长的连续1子串的长度。
比如，对于串00101110110，最长连续1子串的长度是3。它由第5到7个字符组成。
怎么解决呢？我们用一个数组a[1..n]来记录这个01串，然后，我们用一个数组f[0..n]来记录子问题的结果。我们定义f[i]为以第i个字符结尾的连续1子串的长度。假设我们已经求出了f[i-1]。那么，如果a[i]=1，f[i]=f[i-1]+1，否则f[i]=0。初始的f[0]=0。最后，我们扫描f数组，找到最大的值就是答案。
扩展：假如我们给出的是一个01矩阵，那么我们的a数组将变成2维，而其转移方式是没有变化的。不过，这次我们不仅考虑横向的连续1，还考虑纵向的。所以需要两个数组：row[0..n,0..n]和col[0..n.0..n]。那么，转移方式如下：
row[i,j-1]+1 (a[i,j]=1)
row[i,j]=
0 (a[i,j]=0)
col[i-1,j]+1 (a[i,j]=1)
col[i,j]=
0 (a[i,j]=0)
上面的连续的1是同行或同列的。那么，你能想到对角线方向连续的1的长度怎么求么？
子问题2：最大子正方形
给定一个01矩阵，求其中最大的一个子正方形，要求这个正方形全部由0组成。
首先，我们用上面的方法，求出每个点向左扩展的连续0的长度，向上扩展的连续0的长度。不妨依然用row和col两个数组表示。
通过观察，我们找出图形之间的继承关系。如果以(i-1,j-1)点为右下角的最大子正方形的边长是dp[i-1,j-1]，那么以(i,j)为右下角的最大子正方形的边长不会超过dp[i-1,j-1]+1。此外，它还受到row[i,j]和col[i,j]的限制，不会超过这两个数。由于正方形的图形性质，以上三个限制条件是显然的。
dp[i-1,j-1]+1
dp[i,j]= min row[i,j]
col[i,j]
经典题目：USACO 5.3.4 Big Barn
子问题3：最大子1*2矩形
给定一个01矩阵，求其中最大的1*2长方形，要求这个长方形只能包括0。求长方形的尺寸（我们规定高为其尺寸）。
首先，我们用上面的方法，求出row数组和col数组。我们用dp[i,j]表示以（i，j）为左下角的最大子1*2矩形的高。那么，我们发现，其继承关系为：
dp[i-1,j-2]+1
dp[i,j]= min row[i,j] div 2
col[i,j-1]
col[i,j]
经典题目：刘思壮18岁生日模拟赛 雪地留名
子问题4：最大子p*q矩形(p,q互质)
给定一个01矩阵，求其中最大的p*q长方形，要求这个长方形只能包括0。求长方形的尺寸（我们规定高除以p为其尺寸）。
类似上面的转移。但是，这次我们需要更多的继承关系，具体为：
dp[i-p,j-q]+1
row[i-p+1,j] div q
row[i-p+2,j] div q
dp[i,j]= min ………………
row[i,j] div q
col[i,j-q+1] div p
col[i,j-q+2] div p
………………
col[i,j] div p
子问题5：最面积大子矩形
*这个很重要！
给定一个01矩阵，求其中面积最大的全零矩形的面积。
这个问题有两种解法，请参见NOI2003集训队员王知昆冬令营论文《浅谈用极大化思想解决最大子矩形问题》
悬线法解决最大子矩形问题是一个很难的问题，大家一定要掌握。
经典题目：USACO 6.1.2 Rectbarn
Vijos1255 月饼盒
子问题6：最大子三角形
给定一个01矩阵，找出其中最大的全零等腰直角三角形。由于三角形的形状可能不同，我们一一讲解。
为了简便，我们用从当前点经过直角顶点到另一个45度角点的路径来定义三角形形状。
6.1 上——左 三角形
我们用col[i,j]表示从当前点向上连续1的个数，dp[i,j]表示以（i，j）为右下角顶点的 上——左 三角形的直角边长。
dp[i-1,j-1]+1
dp[i，j]=min
col[i,j]
6.2 上——右 三角形
dp[i-1,j+1]+1
dp[i，j]=min
col[i,j]
6.3 下——左 三角形
这次我们在计算col数组时，i循环倒着来。这样，我们算出的col[i,j]表示从一个点向下连续1的个数。
dp[i+1,j-1]+1
dp[i，j]=min
col[i,j]
6.4 下——右 三角形
dp[i+1,j+1]+1
dp[i，j]=min
col[i,j]
6.5 左上——左下 三角形
我们开tmp[0..n,0..n]数组，tmp[i,j]表示以（i，j）为右下角的主对角方向连续0的个数。那么，tmp[i，j]=tmp[i-1，j-1]+1(a[i，j]=1) or 0 (a[i，j]=0)
转移方程为：
dp[i,j-1]+1
dp[i,j]= min
tmp[i,j]
其他的方向的三角形类似，这里就不一一列举了。
子问题7：最大子菱形
给定一个01矩阵，求其中最大的全零菱形的边长。
我们用tmp1[i,j]表示以（i,j）为右下角的主对角方向连续0的长度，用tmp2[i,j]表示以（i,j）为左下角的副对角方向连续0的长度。dp[i,j]为以（i,j）为下顶点的最大菱形边长。那么，我们可得到以下转移方程：
dp[i-1,j]+1
dp[i,j]= min dp[i-2,j]+1
tmp1[i,j]
tmp2[i,j]
观察图形，红色的表示连个对角线方向的连续的长度。蓝色和绿色表示规模小一的菱形，黄色和绿色同样表示规模小一的菱形。绿色部分是两个菱形的相交部分。可见，菱形的继承比较复杂。
网友评论：
 | 1 old_waying 于 2010-05-11 14:01:34 说： | 回复 |
|---|---|---|
宋牛这些日子学得真多啊，膜拜一下，比我强不少呢
| ||
 | 2 claire_ 于 2010-05-12 10:54:18 说： | 回复 |
我也来膜拜rc神牛的
| ||
| 3 lonelycorn 于 2010-05-14 23:33:18 说： | 回复 |
我是酱油
|