直接开始写不废话。1. 这道题到底在问什么从夺回土地说起第一次在 UVA 题库里看到 10074 这道题时我的第一反应是被标题吸引住了。Take the Land夺回土地听起来像是某种策略游戏但这其实是 IOI/ACM 竞赛里非常经典的一道二维动态规划题目。它的核心题意我用自己的话复述一遍你有一块矩形土地被划分成一个 M 行 N 列的网格。每个格子里有 0 或者 1代表这块地是否适合耕种适合是 1不适合是 0。现在要在这片土地上圈出一块矩形区域条件是这片区域里每一格都必须适合耕种也就是全 1。问能圈出的最大矩形面积是多少这道题最朴素的想法是什么枚举。枚举矩形的左上角坐标 (r1, c1) 和右下角坐标 (r2, c2)然后验证这个矩形内部是否全部为 1。这个做法的复杂度是多少光是枚举四个边界就已经是 O(M²N²) 了再加上验证内部全 1又是 O(MN)整体瞬间变成 O(M³N³)。哪怕输入规模只有两位数这个算法也跑不动。学算法最忌讳的就是拿到题直接枚举把问题抽象能力丢掉。所以这道题真正考察的是如何把二维的矩形最值问题巧妙地降维成一维的最大子段和问题。这也是标题里最大子段和DP的由来。我第一次做这题时花了不少时间才想明白这个降维的关键一旦想通代码量其实很少逻辑也很顺。这篇文章就把完整的思考链路讲透从为什么能降维到怎么用 DP 求最优矩形再到具体代码实现和边界问题一步都不跳。2. 经典解法拆解为什么逐行合并是这道题的题眼解决 UVA10074 的核心突破点在于发现一个事实一个矩形区域可以看作若干连续行的叠加。假设我们圈出来的矩形从第 i 行开始到第 j 行结束包含的列范围是某一列到另一列。如果我们把第 i 行到第 j 行的每一列分别做按位与或者求和会发生什么因为矩形内部要求全 1所以对于某个具体列来说从第 i 行到第 j 行这一列上对应的格子必须是 1矩形才能包含这一列如果这一列上有任何一个格子是 0那矩形就不能包含这一列。那么问题就转变成我把第 i 行到第 j 行每一列的格子值加起来得到一个新的一维数组这个数组的第 k 个元素表示第 k 列在 i 行到 j 行这个区间内有多少个 1。如果这个值等于 (j - i 1)说明这一列可以完整包含在矩形里如果小于这个值说明这一列至少有一个 0不能包含。但这里有个更巧妙的做法很多题解用的不是求和等于区间长度这个判断而是直接求和然后利用最大子段和的思路只不过题目里通常是求最大连续和我们这里是求在一维数组里找一段连续区间使得这段区间所有列的和能代表的矩形面积最大。等一下这里有个细节必须说清楚。如果直接对二维矩阵做行区间压缩得到的一维数组元素是列和列和本身并不是 0/1 值。例如某列在 3 行区间内的和是 2说明这列有 2 个 11 个 0那么这个列就不能作为矩形的一部分。但如果一维数组代表的是列和最大子段和可能会把这种含有 0 的列也算进一段连续和里导致结果里偷偷包含了坏格子这是错的。所以正确的处理方式是在做行区间压缩时对每一列做判断。如果第 k 列在第 i 行到第 j 行之间全部是 1我们就把这一列视为可选列在对应一维数组里记一个权值比如记为 1或者记为这列全 1 时的面积贡献只要有一个 0就记为负无穷或者直接记为 0让最大子段和算法忽略它。这样一来一维数组里的每个位置只有两个状态这一列能安全使用和这一列不能使用。这是保证正确性的关键很多初学动态规划的人第一次写挂就是挂在这个地方。我再换一种更直观的表达。用二维前缀和也能做判断预处理出二维前缀和那么任意子矩形内 1 的个数可以用 O(1) 算出来。要求矩形全 1矩形面积就必须等于矩形内 1 的个数。这个思路可以做不过如果逐行合并时每次都去查前缀和代码写起来反而绕。更朴素也更干脆的做法是在枚举上下边界 i 和 j 时用一个临时数组 col[k] 累加从 i 到 j 每一行第 k 列的值同时用一个布尔数组 all_one[k] 记录这一列是否全部为 1。只要 col[k] 等于已经合并的行数就说明该列全 1。这个判断在枚举过程中是顺带完成的。核心方法就这么几句话下面我把完整的推导过程、复杂度分析和一段可以直接照着写的 C 代码放出来。3. 从一维最大子段和到二维最大全 1 矩形一步步推3.1 最大子段和算法的本质先说一维版本因为二维版本最终会调用它。给定一个数组 a[1..n]求一个连续子数组使它的和最大。经典做法是用 Kadane 算法也就是在线性扫描中维护一个当前累加和 cur以及历史最大和 bestcur 0 best -inf for x in a: cur max(x, cur x) best max(best, cur)这个算法的精妙之处在于每个位置只有两种决策要么另起炉灶从当前位置开始一个新的子段要么接着前面的子段继续加。这种决策完美契合无后效性——当前位置之前怎么选的只影响当前的累积值不影响之后的选择。所以它本质上是动态规划只不过把空间压缩成了两个变量。为什么必须这样写而不能在二维问题里直接对列和数组做 Kadane我刚才已经强调了列和数组里不是 0/1可能包含部分 1。Kadane 算法会喜欢和大的子段但因为列和最大也才等于行区间长度对于全 1 矩形的判断它缺少是否全部为 1这个约束。所以我在代码里通常用这样的技巧tmp[k] (rowmin到rowmax之间第k列全为1) ? 行区间长度 : 0;注意我给它赋值成行区间长度而不是简单的 1。为什么要这样因为最终矩形面积等于行数 × 列数即 (j - i 1) × (r - l 1)。如果 tmp[k] 表示包含第 k 列时的每列行数贡献那么一段连续可选列 [l, r] 的临时和就是 (r - l 1) × (j - i 1)再跟全局答案取最大值。但如果直接用 1 表示可选列列数就是连续可选列数最后乘上行数也是同样的效果。两种写法等价只是为了后面代码里少乘一次更多人喜欢在 Kadane 结束后再统一乘。各有各的好处。3.2 枚举上下边界压缩成一维完整的推导过程用一组嵌套循环描述就是这样枚举矩形上边界 top从 0 到 M-1假设下标 0 开始。初始化一个长度为 N 的数组 tmp全部元素置 0。tmp[k] 的含义是在当前 top 到 bottom 这个行区间内第 k 列是否全 1如果全 1则当前的贡献为 bottom-top1否则为 0。枚举下边界 bottom从 top 到 M-1。在这一层循环里我们逐列更新 tmp 数组。怎么更新不是每次重新求连续行区间内的列和而是利用增量更新在 bottom 从 top 向下移动的过程中每次多纳入一行。对于第 k 列只有当新的这一行的第 k 个元素是 1 且之前 tmp[k] 也处于全 1 状态时我们才认为这个列在 [top, bottom] 区间仍然全 1于是给 tmp[k] 增加 1或保持行区间长度只要这一列在新加入的行上遇到 0就把它标记为不可用。对当前 tmp 数组运行 Kadane 算法得到一个最大连续和 curBest。用它更新全局答案 ans。这个增量更新的过程非常优雅。我们不需要真的用一个二维前缀和反复查询只需要在 bottom 不断下移的同时对每一列维护一个是否全 1的标志位。这个标志位有一个性质一旦在某个 bottom 行遇到 0在更大的 bottom 下它永远是 0因为矩形的行区间只会变大不会变小。这意味着 tmp[k] 的值在固定 top 时是单调不增的它从行数变成 0 后就不会复活。3.3 为什么正确把每一列看成能否竖着贯通的候选工具我再用一个生活化的类比帮助理解。想象你在玩一个类似俄罗斯方块的拼图游戏矩形必须完整覆盖一些列。每一列就像一根柱子从 top 行往下插只要中间遇到 0这根柱子就断了不可用。我们在固定 top 时bottom 不断下沉实际上就是在测试如果把矩形下边界定在 bottom那么哪些列的柱子还没断这些连续的未断列就构成一个宽度为 W 的候选块高度是 bottom-top1面积是两者的乘积。Kadane 算法就是帮我们在一大堆候选块里找出宽度最有利的一段。如果某根柱子断了它不可能出现在任何更大的 bottom 候选块里所以我们在 Kadane 里给它赋 0让它不能成为最大连续和中的一部分这个操作完全正确。如果所有柱子都断了那 tmp 全为 0Kadane 的结果也是 0表示当前 top/bottom 下没有可用的矩形不更新 ans。这种枚举上边界 动态下边界 每列增量标记 一维 Kadane的组合本质上就是二维最大全 1 矩形问题的通用框架。想通了这一点UVA10074 就再也没有什么秘密了剩下的只是把细节写对。4. 完整代码实现与关键细节我下面给出一个 C/C 风格的实现。变量命名尽量直观适合竞赛现场快速书写。注意 UVA 的输入格式多组数据每组数据开头两个整数 M 和 N然后是一个 M 行 N 列的 0/1 矩阵。当读到 0 0 时结束。输出最大的全 1 矩形面积。#include cstdio #include cstring #include algorithm using namespace std; const int MAXN 105; int grid[MAXN][MAXN]; bool canUse[MAXN]; // 当前行区间内第 j 列是否全 1 int main() { int M, N; while (scanf(%d%d, M, N) 2 M N) { for (int i 0; i M; i) { for (int j 0; j N; j) { scanf(%d, grid[i][j]); } } int ans 0; for (int top 0; top M; top) { // 初始化从 top 这一行开始每个格子自己决定 canUse for (int j 0; j N; j) { canUse[j] (grid[top][j] 1); } // bottom 从 top 开始可以只包含 top 这一行 for (int bottom top; bottom M; bottom) { if (bottom top) { // 更新 canUse当前 bottom 行加入后哪些列仍然全 1 for (int j 0; j N; j) { if (canUse[j]) { if (grid[bottom][j] ! 1) { canUse[j] false; } } } } // 对 canUse 数组做 Kadane统计最大连续可选列数 int cur 0, best 0; for (int j 0; j N; j) { if (canUse[j]) { cur 1; // 这里的 1 是宽度 best max(best, cur); } else { cur 0; // 遇到断列直接从 0 重来 } } int height bottom - top 1; ans max(ans, best * height); } } printf(%d\n, ans); } return 0; }这个版本里我用的 canUse 是 boolKadane 时的数组元素就是 0 或 1cur 累加的就是宽度连续可选列数。计算面积时用 best最大宽度乘上当前的行区间高度 height。这个思路非常干净不需要维护额外的加权数组。某些简化版题解里喜欢用整型数组 colSum 来记录列高度然后每当一行有 0 就把 colSum 清零效果一样。我之所以用 bool 版本是因为它跟题意更贴合能让读者明确意识到我们追踪的是列是否可用这个二元状态不是列里有多少个 1。几个容易踩的细节第一初始化 canUse 的位置。我是在 top 循环内、bottom 循环外做了初始化把 canUse 设为 grid[top][j] 1。然后在 bottom 循环内部用 if (bottom top) 做增量更新。如果漏掉这个 if在 bottom top 时仍去执行更新等于把当前行更新了两遍不会出大错但逻辑不够干净。如果你选择在外面全初始化为 true然后在 bottom 循环内逐行更新也没问题但要小心 top 行本身是 0 时必须立刻清掉对应列的 canUse不然会误判。第二Kadane 部分的 cur 累加时累加的是宽度 1不是高度。高度已经通过 height 变量在每次面积计算时乘进去了。如果你让 cur 累加高度最后就不乘两种方式都可以但千万别把高度既累加又到最后乘那会重复计算导致答案虚高。第三ans 初始化为 0 是最稳的。考虑到最坏情况矩阵全为 0最好的合法矩形面积是 0。不能把 ans 初始化为负数再对 0 取 max那样虽然也不会错但显得多余。5. 复杂度分析与程序运行流程验证5.1 三层循环为什么已经足够优整个实现是三层循环外层 top 从 0 到 M-1中层 bottom 从 top 到 M-1内层 j 从 0 到 N-1。复杂度是 O(M²·N)。如果 M 和 N 的规模都在 100 以内这个模型大概是 1e6 量级在 UVA 的测试数据下完全没问题。有些人担心这个算法不是最优因为固定一个 topbottom 每次下移都要重新扫一遍 j。但实际上这已经是非常经典的解法了因为我们需要在 bottom 变化时动态维护 canUse 数组不内层扫 j 无法做到增量更新。能用 O(M²·N) 解决的二维矩阵最值问题通常已经能满足竞赛时限。如果题目把 M 和 N 的规模提高到 1000 以上这个 O(M²·N) 就会卡住那就要考虑悬线法最大子矩形或者极大化思想复杂度可以降到 O(M·N)。但 UVA10074 的约束决定了 O(M²·N) 是主流解而且思路上来讲从最大子段和切入比从悬线法切入更自然这也是标题特意标出最大子段和DP的原因。5.2 用一个小矩阵手工推演我就不拿输入样例搞这种破坏了自己构造一个规模小但能检验算法正确性的例子。假设 M 3N 4矩阵为1 0 1 1 1 0 1 1 1 1 1 0肉眼能看出最大全 1 矩形在第 0 行到第 2 行列 2 和列 3 组成的 3×2 矩形面积 6。但注意第 3 列下标 3在第 2 行是 0所以列 3 不能贯穿所有三行。还有一个 3×2 矩形是列 1 和列 2但列 1 在第 0 行第 1 列是 0也不行。实际上最大的可能是第 0 到第 1 行列 2 和列 3面积 2×24以及第 1 到第 2 行列 0、列 2、列 3但列 0 在第 2 行是 1、第 1 行是 1第 2 列是 1第 3 列第 2 行是 0所以也不对……我干脆直接跑一下算法逻辑top0:bottom0: canUse {1,0,1,1}, Kadane 最大连续宽度 2列 2 和列 3height1best_area2。bottom1: canUse 更新后 {1,0,1,1}因为第 1 行和 top 行一致最大连续宽度 2height2面积 4。bottom2: canUse 更新后 {1,0,1,0}列 3 在第 2 行为 0最大连续宽度 1列 2height3面积 3。top1:bottom1: canUse {1,0,1,1}height1面积 2。bottom2: canUse 更新后 {1,0,1,0}列 2 可贯通height2面积 2。top2:bottom2: canUse {1,1,1,0}最大连续宽度 3列 0 到列 2height1面积 3。全程最大面积 4。等一下我肉眼看的那个 4 是对的但前面我说最大可能是 6 是错的因为列 1 不是全 1列 3 在 bottom2 时断了。所以全局最大其实是 top0,bottom1,宽度2,高度2 的 4以及 top0,bottom0,宽度2 的 2还有 top2,bottom2,宽度3 的 3最终答案是 4。虽然我一开始肉眼观察错了但这恰好说明算法不会放过任何细节也提醒读者写题时不要只靠直觉。这个例子也验证了增量更新 canUse 数组的正确性。6. 从这道题延伸出去的三个常见变体与进阶思考6.1 统计子矩形数量而不是最大面积如果题目改成求有多少个全 1 子矩形那么单纯的最大子段和思路就不够用了。因为最大子段和只关心最值不关心所有可能的连续段。这时需要枚举每个 1 作为矩形的右下角维护向上连续 1 的高度数组再用单调栈计算以该行为底边的合法矩形数量。这是另一个经典套路。从 UVA10074 出发搞懂了最大面积后可以尝试这个升级版能把单调栈的应用也练熟。6.2 最大全 1 正方形如果要求矩形必须是正方形那么可以用 DP 做设 dp[i][j] 表示以 (i,j) 为右下角的最大正方形边长转移方程是取左、上、左上三个方向的最小值再加 1。这个专题和最大子矩阵经常混在一起考但两者的复杂度差异巨大。正方形的朴素 DP 是 O(M·N)矩形问题是 O(M²·N)。不少同学在面对矩形问题时会条件反射地套正方形的 DP结果做不出来。理解了 UVA10074 之后你会更清楚为什么矩形问题不能用那个简单的 DP——因为矩形有两个维度是可变的必须额外枚举其中一个维度。6.3 带障碍物的最大空矩形还有一些题矩阵里的 0 表示空地1 表示障碍物求最大全 0 矩形。这种题目和求最大全 1 矩形本质上一样要么把 0/1 全部取反后再跑同一个算法要么直接改判断条件。这说明这类问题的核心不是 0 和 1 谁代表好而是全好矩形这个约束的判定方式。把它抽象出来就是任意给定一个好坏标记矩阵找一个内部全好的最大矩形。UVA10074 作为这个模型的原型题非常有代表性。6.4 如果把草地问题变成允许一定比例坏格子的最大矩形有些生产场景比如规划种植区或广告牌投放区域会允许矩形内有一定比例的坏格子。这时最大子段和的要么全好、要么完全抛弃策略就不再适用。一种做法是把坏格子视为负权值好格子为正权值然后用二维前缀和二分答案枚举边长。这种做法和今天讲的全 1 矩形是两个思路但核心都是如何高效地把一个矩形区域内部某个统计量算出来。把这道题的降维思想融会贯通后再做这些变体会自然很多。7. 我在 UVA10074 上踩过的三个坑第一个坑也是最容易的底层更新列状态时我一开始写的是tmp[j] grid[bottom][j]然后判断tmp[j] bottom-top1。这个写法在行区间高度为 1 时没问题高度大于 1 时如果一行有 1、一行有 0tmp[j] 的累加值可能小于高度但大于 0Kadane 会错误地把这列当作可以贡献面积的列加进连续段。后来我改成 bool 型 canUse用只要碰到 0 就永久置 false的策略才彻底杜绝了半好列混入的问题。竞赛题里一个错误的初始化或累加逻辑往往会把小样例跑对、大样例跑挂这个坑很典型。第二个坑遗忘 top 循环里对 canUse 的初始化。第一次写的时候我把 canUse 定义在 top 循环外面导致 top1 时canUse 还残留着 top0 的数据。于是 bottom1 时某些列明明在 top1 行是 0canUse 却还是 true错误地让算法以为这些列可以从 top1 一直贯通到 bottom1。这属于典型的状态未归零错误。调试方法也很简单就是构造一个竖着方向有断层的矩阵比如某行有一个 1隔一行是 0再隔一行又是 1专门检查状态是否被错误延续。第三个坑读入多组数据时忘记处理 M0, N0 的终止条件导致死循环或数组越界。UVA 的老式判题系统习惯了这种终止标记第一次从其他 OJ 转过来的同学容易忽略。写while (scanf(%d%d, M, N) 2 M N)即可避免。总结一下我的体会UVA10074 这道题不复杂但它特别适合用来检验你有没有真正掌握二维问题降维成多个一维问题的思维模式。最大子段和的代码只有几行难的是你能意识到先固定行区间再把每一列压成一个标志位最后用 Kadane 找出最优列区间。只要你把这条链路彻底打通以后遇到任何二维矩形约束题都会本能地想到这个框架。最后再说一句做竞赛题不能光看题解一定要亲手把代码敲一遍、用边界数据跑一遍比如全 1 的矩阵、单行矩阵、单列矩阵、交替 0/1 的棋盘矩阵都测一遍再提交。这是我刷 UVA 系列最深刻的体会。