Vijos 1351 棋盘制作 解题报告

由于第一问所求的正方形必定包含在所有极大子矩形中，因此利用极大化思想可以在O(nm)的时间复杂度内求出最大子矩形，在枚举所有极大子矩形的过程中记录下最大的较短边长度，其平方即是第一问的答案。

简单地说一下在O(nm)的时间复杂度内枚举所有极大子矩形的算法，枚举棋盘上的每个棋子，先求出其向上、向左和向右最大可拓展到的位置，分别用h[i,j]、l[i,j]和r[i,j]记录。然后再枚举一次全部棋子，若h[i,j]>1则l[i,j]=max(l[i,j],l[i-1,j]),r[i,j]=min(r[i,j],r[i-1,j])。这样既可得到每个棋子在其向上拓展最高的前提下的极大子矩形，这样就包含了所有的极大子矩形。

R1134170 Accepted 100 From IwfWcf－ P1351 FPC Vijos Dolphin 2009-2-5 9:54:59