区间动态规划例题：最大矩形覆盖问题

题目描述
给定一个由 0 和 1 组成的二维矩阵，矩阵中可能包含多个由 1 组成的连通区域（“矩形”），每个矩形是轴对齐的，且矩形之间不重叠（矩形之间至少隔一行或一列）。现在允许选择一个矩形区域，将其中的所有 1 清除（即置为 0），但清除操作的成本等于该矩形区域的面积。问：清除所有 1 的最小总成本是多少？

示例：
矩阵：

1 1 0 0 0  
1 1 0 1 1  
0 0 0 1 1  
0 0 0 1 1  

说明：矩阵中有两个矩形区域：

• 左上角的 2×2 矩形（坐标 (0,0)-(1,1)），面积为 4。
• 右下角的 2×3 矩形（坐标 (1,3)-(3,5)），面积为 6。
  目标：选择若干矩形覆盖所有 1，使得覆盖矩形的总面积最小（每个矩形必须完全覆盖一个 1 的连通区域，且矩形之间可以合并覆盖）。
  注意：允许用更大的矩形覆盖多个小连通区域（只要矩形内全是 1 或 0 均可），但矩形内若包含 0，则覆盖成本会增大（因为矩形的面积会计入所有格子，包括 0）。
  本题要求最小化总覆盖面积，即找到一组矩形，覆盖所有 1，且矩形总面积最小。

解题思路
这是一个二维区间动态规划问题。我们可以先将问题转化为：

1. 找出所有由 1 组成的连通区域（即每个连通分量是一个轴对齐矩形，因为题目说明矩形之间不重叠）。
2. 然后问题变为：用若干个矩形覆盖所有这些矩形区域，矩形可以合并（即用一个更大的矩形覆盖多个区域，但大矩形内可能包含 0，这样会增加成本），求最小总面积。

更一般地，我们可以对矩阵的整个范围 [r1, r2]×[c1, c2] 进行动态规划，定义 dp[r1][c1][r2][c2] 为覆盖该子矩阵内所有 1 的最小面积。但这样状态数是 O(n^4)，其中 n 是矩阵边长，当 n ≤ 50 时可行。

详细步骤

第1步：预处理连通区域
扫描矩阵，找出所有由 1 组成的连通区域。由于矩形不重叠且轴对齐，每个连通区域可以用其最小行 r_min、最大行 r_max、最小列 c_min、最大列 c_max 表示，且该矩形内全是 1（否则不连通）。
将这些矩形存入列表 rects。

第2步：定义DP状态
定义 dp[r1][c1][r2][c2] 表示覆盖子矩阵 (r1,c1) 到 (r2,c2) 内所有 1 的最小总面积。
初始化：

• 如果子矩阵内没有 1，dp = 0。
• 如果子矩阵恰好完全包含某个矩形区域（即该矩形区域的所有格子都在子矩阵内），则 dp = (r2-r1+1)*(c2-c1+1)（即用整个子矩阵覆盖它）。

第3步：状态转移
考虑如何覆盖子矩阵 [r1,r2]×[c1,c2] 内的 1：

• 方案一：直接用整个子矩阵覆盖，成本 = 面积 (r2-r1+1)*(c2-c1+1)。
• 方案二：在中间某行 k（r1 ≤ k < r2）切开，将子矩阵分成上下两部分，分别覆盖，成本 = dp[r1][c1][k][c2] + dp[k+1][c1][r2][c2]。
• 方案三：在中间某列 k（c1 ≤ k < c2）切开，分成左右两部分，成本 = dp[r1][c1][r2][k] + dp[r1][k+1][r2][c2]。

取这三种方案的最小值。

为什么这样转移正确？
因为覆盖矩形可以任意划分，切割行或列相当于用多个矩形覆盖，且每个矩形是轴对齐的。动态规划考虑所有可能的切割位置，取最优解。

第4步：填表顺序
按子矩阵的行数、列数从小到大计算。
伪代码：

for len_r = 1 to rows:
    for len_c = 1 to cols:
        for r1 = 0 to rows-len_r:
            for c1 = 0 to cols-len_c:
                r2 = r1+len_r-1
                c2 = c1+len_c-1
                // 检查子矩阵内是否有1
                if 没有1: dp=0
                else:
                    // 方案一
                    cost = (r2-r1+1)*(c2-c1+1)
                    // 方案二：切行
                    for k = r1 to r2-1:
                        cost = min(cost, dp[r1][c1][k][c2] + dp[k+1][c1][r2][c2])
                    // 方案三：切列
                    for k = c1 to c2-1:
                        cost = min(cost, dp[r1][c1][r2][k] + dp[r1][k+1][r2][c2])
                    dp[r1][c1][r2][c2] = cost

最终答案 = dp[0][0][rows-1][cols-1]。

第5步：复杂度优化

• 状态数 O(n^4)，转移 O(n)，总 O(n^5) 可能太大（n=50时约为 3e9）。
• 优化：预处理每个子矩阵是否包含 1（用前缀和），切割时只考虑包含 1 的切割点。
• 进一步优化：注意到切割点只需要在矩形边界处（即某个连通区域的上下或左右边界），这样可以减少切割点的数量。

举例说明
用开始的例子：
矩阵 4×5，两个矩形区域：
Rect1: (0,0)-(1,1)
Rect2: (1,3)-(3,5)

计算 dp[0][0][3][4]：

• 方案一：用整个矩阵覆盖，面积=20。
• 方案二：切行 k=1：
  上部分 dp[0][0][1][4]：覆盖 Rect1 和 Rect2 的一部分（Rect2 在第1行有部分），需要单独算。
  实际上，dp[0][0][1][4] 可切列 k=2：左边覆盖 Rect1（面积4），右边覆盖 Rect2 的一部分（面积22=4），总8。
  下部分 dp[2][0][3][4]：覆盖 Rect2 的剩余部分（面积22=4）。
  总成本 8+4=12。
• 方案三：切列 k=2：
  左部分 dp[0][0][3][2]：只有 Rect1（面积4）。
  右部分 dp[0][3][3][4]：只有 Rect2（面积6）。
  总成本 4+6=10。
  最终最小成本 = min(20, 12, 10) = 10。

因此，最佳方案是分别用两个矩形覆盖各自区域，总成本=4+6=10。

总结
本题通过二维区间DP，枚举所有可能的矩形覆盖方式，并利用切割行/列将问题分解为更小的子问题，从而得到最小总面积。关键在于理解覆盖矩形的灵活性和切割的完备性。