最大子图形问题详解
发表时间:2010-05-04 20:09:46 浏览(4759) 评论(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 说: | 回复 | |
我是酱油
|