2216.[NOIP2014 普及组] 子矩阵

算法思路

1. 问题分析

本题需要从给定的 $n \times m$ 矩阵中选出 $r$ 行 $c$ 列的子矩阵，使得子矩阵的分值（相邻元素差的绝对值之和）最小。由于数据范围较小（$n, m \leq 16$），可以采用组合枚举和动态规划相结合的解法：

• 组合枚举：枚举所有可能的 $c$ 列组合
• 动态规划：在选定列组合后，通过动态规划选择最优的 $r$ 行

2. 解决策略

1. 枚举列组合：使用递归或组合库生成所有 $c$ 列的组合
2. 动态规划预处理：
   • 计算单行内相邻元素的差（左右相邻）
   • 计算两行间对应列的差（上下相邻）
3. 动态规划状态设计：
   • dp[i][j] 表示前 i 行中选择 j 行（包含第 i 行）的最小分值
   • 状态转移：dp[i][j] = min(dp[k][j-1] + cost(k, i))，其中 cost(k, i) 包含：
     • 第 i 行内相邻元素的差
     • 第 k 行与第 i 行对应列的差
4. 结果计算：对每个列组合计算最小分值，取全局最小值

3. 复杂度分析

• 时间复杂度：
  • 列组合枚举：$O(C(m, c))$，最坏 $C(16,8)=12870$
  • 动态规划：$O(n^2 \times r \times c)$，最坏 $16^3 \times 16=65536$
  • 总复杂度：$O(C(m,c) \times n^2 \times r \times c)$，最坏约 $8.4 \times 10^8$
• 空间复杂度：$O(n \times r)$ 存储动态规划状态

---

代码实现

C++解法

cpp
复制
1#include<iostream>
2#include<cstdio>
3#include<cstring>
4#include<cmath>
5#include<algorithm>
6using namespace std;
7
8int lr[100];           // 标记选择的列
9int f[100][100];       // dp状态表：f[i][j]表示前i行选j行(含i)的最小分值
10int a[100][100];       // 存储输入矩阵
11int n, m, r, c, ans = 1e9;
12
13// 递归枚举列组合
14// x: 当前选择的列起始位置，num: 已选择的列数
15void search(int x, int num) {
16    if (num == c) {  // 已选够c列
17        // 初始化dp状态为极大值
18        memset(f, 0x3f, sizeof(f));
19        for (int i = 0; i <= n; i++) f[i][0] = 0;
20        
21        // 计算只选1行的情况（行内相邻差）
22        for (int i = 1; i <= n; i++) {
23            f[i][1] = 0;
24            int last = 0;
25            for (int j = 1; j <= m; j++) {
26                if (lr[j]) {  // 只处理选中的列
27                    if (last) {
28                        f[i][1] += abs(a[i][j] - last);  // 行内相邻差
29                    }
30                    last = a[i][j];
31                }
32            }
33        }
34        
35        // 动态规划：从第2行开始选择
36        for (int j = 2; j <= r; j++) {
37            for (int i = j; i <= n; i++) {
38                for (int k = 1; k < i; k++) {
39                    int tot = 0;
40                    int last = 0;
41                    // 计算新增代价：行间差+行内差
42                    for (int l = 1; l <= m; l++) {
43                        if (lr[l]) {
44                            tot += abs(a[i][l] - a[k][l]);  // 行间相邻差
45                            if (last) {
46                                tot += abs(a[i][l] - last);  // 行内相邻差
47                            }
48                            last = a[i][l];
49                        }
50                    }
51                    f[i][j] = min(f[i][j], f[k][j-1] + tot);  // 状态转移
52                }
53            }
54        }
55        
56        // 更新全局最小值
57        for (int i = 1; i <= n; i++) {
58            ans = min(ans, f[i][r]);
59        }
60        return;
61    }
62    
63    // 递归枚举列组合
64    for (int i = x + 1; i <= m; i++) {
65        lr[i] = 1;
66        search(i, num + 1);
67        lr[i] = 0;
68    }
69}
70
71int main() {
72    scanf("%d%d%d%d", &n, &m, &r, &c);
73    for (int i = 1; i <= n; i++) {
74        for (int j = 1; j <= m; j++) {
75            scanf("%d", &a[i][j]);
76        }
77    }
78    search(0, 0);  // 从第0列开始枚举
79    cout << ans;
80    return 0;
81}

代码解释：

1. 函数参数说明：
   • search(x, num)：递归枚举列组合，x 为当前选择起始列，num 为已选列数
   • f[i][j]：动态规划状态表，表示前 i 行选 j 行的最小分值
2. 核心逻辑解析：
   • 列组合枚举：递归生成所有 $C(m, c)$ 种列选择方案
   • 单行初始化：计算每行内部相邻元素的差（左右相邻）
   • 状态转移：三重循环更新 f[i][j]，包含行间差（上下相邻）和行内差
   • 边界处理：f[i][0]=0 表示选择0行的分值为0
3. 特殊语法说明：
   • memset(f, 0x3f, sizeof(f))：初始化为极大值（约 $10^9$ 量级）
   • lr[] 数组：标记选择的列（1表示选中）

---

Python3解法

python
复制
1import sys
2from itertools import combinations
3
4def main():
5    # 读取输入：矩阵维度n,m和子矩阵维度r,c
6    n, m, r, c = map(int, sys.stdin.readline().split())
7    # 读取n行m列的矩阵
8    a = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
9    
10    ans = float('inf')  # 初始化全局最小分值为无穷大
11    
12    # 枚举所有列组合（C(m, c)种可能）
13    for cols in combinations(range(m), c):
14        # 初始化dp表：f[i][j]表示前i行选j行(含i)的最小分值
15        f = [[float('inf')] * (r + 1) for _ in range(n + 1)]
16        for i in range(n + 1):
17            f[i][0] = 0  # 选0行的分值为0
18        
19        # 计算单行选择的分值（行内相邻差）
20        for i in range(1, n + 1):
21            f[i][1] = 0
22            last = None
23            for col_idx in cols:
24                if last is not None:
25                    # 累加行内相邻元素差
26                    f[i][1] += abs(a[i-1][col_idx] - last)
27                last = a[i-1][col_idx]  # 更新当前元素
28        
29        # 动态规划：选择多行的情况
30        for j in range(2, r + 1):      # 选择j行
31            for i in range(j, n + 1):   # 当前行i（至少从j开始）
32                for k in range(1, i):   # 上一行k
33                    tot = 0
34                    last = None
35                    # 计算新增代价：行间差+行内差
36                    for col_idx in cols:
37                        # 累加当前行与上一行的列差值（行间差）
38                        tot += abs(a[i-1][col_idx] - a[k-1][col_idx])
39                        if last is not None:
40                            # 累加当前行内相邻列差值（行内差）
41                            tot += abs(a[i-1][col_idx] - last)
42                        last = a[i-1][col_idx]  # 更新当前行元素
43                    # 状态转移：取最小值
44                    f[i][j] = min(f[i][j], f[k][j-1] + tot)
45        
46        # 更新全局最小值
47        for i in range(1, n + 1):
48            ans = min(ans, f[i][r])
49    
50    print(ans)  # 输出最小分值
51
52if __name__ == "__main__":
53    main()

代码解释：

1. 与C++实现差异：
   • 使用 itertools.combinations 直接生成列组合，避免递归
   • Python索引从0开始，需调整矩阵访问（a[i-1][col_idx]）
2. Python特性说明：
   • float('inf')：表示无穷大，用于初始化
   • 列表推导式：快速初始化二维dp表
3. 关键语句解析：
   • for cols in combinations(...)：枚举所有列组合方案
   • 三重循环动态规划：分别处理选择行数、当前行和上一行
   • tot 计算：同时包含行间差（上下相邻）和行内差（左右相邻）

---

复杂度对比

选择建议：

1. C++：在 $n, m \leq 16$ 时效率较高，尤其适合竞赛环境
2. Python：代码简洁，适合数据规模较小（$n, m \leq 12$）的场景
3. 优化方向：预处理行内差和行间差可将动态规划内层循环降为 $O(1)$