USACO/range

来自NOCOW

< USACO

跳转到：导航, 搜索

[编辑] 分析

这道题可以动态规划。二维的动态规划。

状态定义：G[i][j]为以(i,j)为左上角顶点的正方形的最大边长。

边界条件：G[i][j]为初始读入的矩阵。

状态转移方程： G[i][j]=min{ G[i+1][j] , G[i][j+1] , G[i+1][j+1] } + 1;

解析： G[i+1][j] , G[i][j+1] , G[i+1][j+1]分别为(i,j)向下、向右、向右下一格的状况。

在(n-1,n-1)当且仅当三者都为1的时候，正方形才能扩充。从最右下向上，依次扩充即可。 CmYkRgB123 21:32 2008年4月17日 (CST)

这道题也可以直接模拟计算以每个格为左上角顶点的最大正方形的边长: 对每一格,在当前已有的长度为K-1的正方形基础上,若右侧与下侧能同时加上长为K宽为1的矩形条,则得到长度为K的正方形.

在判断是否有完整的矩形条时,先预处理得到从左到右与从上到下的累加数组:

 sum_horizon[i][j]=sum_horizon[i][j-1]+a[i][j];
 sum_vertical[i][j]=sum_vertical[i-1][j]+a[i][j];

并利用等式判断:

 sum_horizon[i+k-1][j+k-1]-sum_horizon[i+k-1][j-1]==K &&
 sum_vertical[i+k-1][j+k-1]-sum_vertical[i-1][j+k-1]==K

算法复杂度O(N3). --[[User:jay23jack] 17:27 2008年7月27日 (CST)

[编辑] 另一算法

opt[i,j]表示以i,j为右下角，可构成的最大正方形的边长

方程为：

 opt[i,j]:=min(opt[i-1,j],opt[i,j-1],opt[i-1,j-1])+1;

再开一数组F，用来统计边长相同的正方形的个数，因为边长小的与边长大的存在包含关系，所以最后将边长大的正方形的个数再累加到边长比它小的正方形内，输出即可。详见代码6 --D.puppet

上面的算法时间复杂度是O(N^2)，我写的带4个二重循环（其中1个是读入）。

①读入；②用上面的算法，注意当读入的矩阵中map[i][j]='0'时，opt[i][j]必定是0；③统计边长相同的正方形（用桶排序的原理）；④按照上面的方法加起来。

虽然时间复杂度是O(N^2)，但是常数比较大。 --Fruderica

O(N^2logN)的一个算法：

枚举左上角后二分确定最大边长.结果处理同上一算法. 详细内容见C++代码2 --cgy4ever

思路同上，不过使用单调队列确定最大边长，时间复杂度为O（N^2），空间复杂度不能优化为O（N），我的Pascal写了70多行...

O（N^3）简单易想算法。 dp[k][i][j]表示以k为边长左上角为（i，j）的正方形是否能构成。那么

dp[k][i][j] = dp[k-1][i][j] && dp[k-1][i][j+1] && dp[k-1][i+1][j] && maze[i+k][j+k]

(maze[i][j]表示矩形点(i,j)的bool值)dp的过程中统计即可。

期中3维数组超内存降维或者用滚动数组。代码见C++

其实这个题可以类比最优子矩阵，只不过求的是所有的矩阵，用类似最优子矩阵的方法枚举所有子矩阵即可，详见pascal代码7

另一思路：

先统计出f[i][j](从（0，0）开始，在长为i，宽为j的范围内障碍的数量)，f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+map[i][j];(map[i][j]:若无障碍为0,有障碍为1)。然后搜索范围（w,r）到(i,j)范围内是否有障碍，即f[i][j]-f[w][j]-f[i][r]+f[w][r]是否为0，累计可得答案。具体代码见C. --by Eagle747