2020-2021:teams:famerwzyyuki:求01矩阵中最大的全为0或1的矩阵
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:famerwzyyuki:求01矩阵中最大的全为0或1的矩阵 [2020/05/22 10:25] wzy2001wzy |
2020-2021:teams:famerwzyyuki:求01矩阵中最大的全为0或1的矩阵 [2020/06/01 19:32] (当前版本) admin ↷ 页面technique:max_matrix被移动并更名为2020-2021:teams:famerwzyyuki:求01矩阵中最大的全为0或1的矩阵 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| + | **格式**： | ||
| + | - 请注意使用数学公式，如复杂度：$O(MN)$，递推公式：$\text{Up}[i][j] = \text{Up}[i-1][j] + 1$。变量如 $n$，$i$。 | ||
| + | - 公式中不要使用全角括号。 | ||
| + | - 代码现在可以放到 wiki 上啦（并使用 ''<hidden></hidden>'' 隐藏），麻烦搬迁一下。 | ||
| + | - 中文请使用全角逗号“，” | ||
| + | |||
| + | **内容**：讲解比较清晰。可否多找几道例题？ | ||
| + | |||
| ====== 求01矩阵中最大的全为0或1的矩形&正方形 ====== | ====== 求01矩阵中最大的全为0或1的矩形&正方形 ====== | ||
| ===== 悬线法dp ===== | ===== 悬线法dp ===== | ||
| ==== 悬线法的用途 ==== | ==== 悬线法的用途 ==== | ||
| - | 针对求给定矩阵中满足某条件的极大矩阵，比如“面积最大的长方形、正方形”“周长最长的矩形等等”。可以满足在时间复杂度为O（M*N）的要求，比一般的枚举高效的多，也易于理解。 | + | 针对求给定矩阵中满足某条件的极大矩阵，比如“面积最大的长方形、正方形”“周长最长的矩形等等”。可以满足在时间复杂度为 O(MN) 的要求，比一般的枚举高效的多，也易于理解。 |
| ==== 悬线法的思路 ==== | ==== 悬线法的思路 ==== | ||
| 悬线法，悬线的定义，就是一条竖线，这条竖线要满足上端点在整个矩形上边界或者是一个障碍点。然后以这条悬线进行左右移动，直到移至障碍点或者是矩阵边界，进而确定这条悬线所在的极大矩阵。也就是说，我们要针对矩阵中每个点进行求极大矩阵的操作，所以我们需要Left[]数组存每个点能到达的最右位置，Right[]数组存放每个点能到达的最左位置，Up[]数组位置。设置好这些数组之后，我们开始遍历矩阵中的每个点ves[i,j]，把每个点和上一个点（ves[i-1][j]）的Left和Right进行比较，分别取最大和最小，Up则是上一个点的Up+1，进而求出面积进行比较。所以我们可以得到相关的递推公式。\\ | 悬线法，悬线的定义，就是一条竖线，这条竖线要满足上端点在整个矩形上边界或者是一个障碍点。然后以这条悬线进行左右移动，直到移至障碍点或者是矩阵边界，进而确定这条悬线所在的极大矩阵。也就是说，我们要针对矩阵中每个点进行求极大矩阵的操作，所以我们需要Left[]数组存每个点能到达的最右位置，Right[]数组存放每个点能到达的最左位置，Up[]数组位置。设置好这些数组之后，我们开始遍历矩阵中的每个点ves[i,j]，把每个点和上一个点（ves[i-1][j]）的Left和Right进行比较，分别取最大和最小，Up则是上一个点的Up+1，进而求出面积进行比较。所以我们可以得到相关的递推公式。\\ | ||
2020-2021/teams/famerwzyyuki/求01矩阵中最大的全为0或1的矩阵.1590114335.txt.gz · 最后更改: 2020/05/22 10:25 由 wzy2001wzy
