用户登录:

用户名:
密码:      

文章分类:


最新评论:

userleijiankun 说:膜拜神牛。……
usercss 说:康拓展开和逆康拓展……
usersongrenchu 说:欢迎大家踊……
userAdmin 说:……

最大子图形问题详解

发表时间:2010-05-04 20:09:46  浏览(2343) 评论(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]



观察图形,红色的表示连个对角线方向的连续的长度。蓝色和绿色表示规模小一的菱形,黄色和绿色同样表示规模小一的菱形。绿色部分是两个菱形的相交部分。可见,菱形的继承比较复杂。
srcoiblog

网友评论:

user1  old_waying 于 2010-05-11 14:01:34 说:回复
宋牛这些日子学得真多啊,膜拜一下,比我强不少呢
user2  claire_ 于 2010-05-12 10:54:18 说:回复
我也来膜拜rc神牛的
user3  lonelycorn 于 2010-05-14 23:33:18 说:回复
我是酱油

Guest 发表评论