形式化题目

给定一个 $n$ 行 $m$ 列的正整数矩阵，从中选出 $r$ 行 $c$ 列（保持行、列的 相对顺序）构成子矩阵。子矩阵的分值是其中每一对上下左右相邻元素之差的 绝对值之和，求所有子矩阵中的最小分值。

记选中的行集为 $R = \{r_1 < r_2 < \cdots < r_r\}$、列集为 $C = \{c_1 < c_2 < \cdots < c_c\}$，分值恰好分成两类边：

样例 1 中选中第 4、5 行与第 1、3、4 列，交叉格加粗如下：

这个 $2 \times 3$ 子矩阵有 3 对纵向相邻（差 $1, 0, 0$）和 4 对横向相邻 （差 $1, 1, 2, 1$），分值为 $6$，即样例输出。

正解

思路

朴素做法：枚举所有行组合与列组合，按定义逐对累加，共 $\binom{n}{r} \cdot \binom{m}{c}$ 对。最坏 $n = m = 16,\ r = c = 8$ 时 $\binom{16}{8}^2 \approx 1.65 \times 10^8$ 对，每对还要 $O(rc)$ 次累加， 显然超时。瓶颈在于列组合这一层：行组合最多 $\binom{16}{8} = 12870$ 个并不可怕， 可怕的是每个行组合都要再乘一个 $\binom{m}{c}$。

关键观察：固定行集 $R$ 后，分值的两部分各自只依赖单侧信息：

• 纵向部分对每个列 $j$ 独立求和，记 $v[j] = \sum_{t=1}^{r-1} \left| a_{r_t j} - a_{r_{t+1} j} \right|$， 只依赖 $R$ 和列 $j$，与选哪些列无关；
• 横向部分只有当列 $i$、$j$ 在子矩阵中相邻时才计入，记 $h[i][j] = \sum_{i' \in R} \left| a_{i' i} - a_{i' j} \right|$， 只依赖 $R$ 和列对 $(i, j)$。

于是固定 $R$ 后

"选 $c$ 个列并求最小"就从组合枚举变成了按从左到右顺序取位置的一维 DP： 取一个列付 $v$，每多接一个列付 $h$。定义

• $dp[1][j] = v[j]$；
• $dp[k][j] = v[j] + \min_{i < j} \big( dp[k-1][i] + h[i][j] \big)$，表示已选 $k$ 个列、最右一个是 $j$ 的最小代价；$i < j$ 保证列下标递增（即保持列的 相对顺序），末位取不到更小位置时该状态为 $\infty$；

遍历顺序先 $k$ 后 $j$（每轮只用上一轮的结果），该行组合的答案是 $\min_{1 \leqslant j \leqslant m} dp[c][j]$，再对所有行组合取最小即全局答案。 固定行组合的代价为 $O(c \cdot m^2)$，总复杂度 $\binom{n}{r} \cdot (r + c) \cdot m^2$。行列对称，同理也可以枚举列、在行上 DP，因此实现里比较 $\binom{n}{r}$ 与 $\binom{m}{c}$，枚举组合数更少的一维 （需要时转置矩阵），另一维留给 DP。

样例 DP 表

下面固定行组合 $(4, 5)$（即样例最优组合），展示 $v = [1, 4, 0, 0, 8]$ 与 三轮 DP 的结果（$\infty$ 表示"选不够 $k$ 个列"的无效状态，单元格是 $dp[k][j]$）：

观察重点：第 $k$ 行只从第 $k-1$ 行中下标更小的位置转移。例如末列 4、已选 3 列的状态：

它的前驱是 $dp[2][3] = 4$（再前驱是 $dp[1][1] = 1$），还原出列集 $\{1, 3, 4\}$。全局对所有行组合取最小后答案为 6，最优行组合正是 $(4, 5)$， 与题面样例的选法一致。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)1000000000000000000LL;
ll comb_count(int n,int r){ if(r<0||r>n) return 0; if(r>n-r) r=n-r; ll ans=1; for(int i=1;i<=r;i++) ans=ans*(n-r+i)/i; return ans; }
void gen_combos(int n,int take,int start,vector<int>&cur,vector<vector<int> >&all){ if((int)cur.size()==take){all.push_back(cur);return;} for(int i=start;i<n;i++){cur.push_back(i); gen_combos(n,take,i+1,cur,all); cur.pop_back();}}
ll best_score(vector<vector<ll> > &mat,int take,int pick){ int height=mat.size(), width=mat[0].size(); vector<vector<ll> > flat(height, vector<ll>(width*width)); for(int r=0;r<height;r++) for(int i=0;i<width;i++) for(int j=0;j<width;j++) flat[r][i*width+j]=llabs(mat[r][i]-mat[r][j]); vector<vector<int> > all; vector<int> cur; gen_combos(height,take,0,cur,all); ll best=INF; for(int ci=0;ci<(int)all.size();ci++){vector<int> combo=all[ci]; vector<ll> v(width); for(int b=0;b<width;b++) for(int z=0;z+1<(int)combo.size();z++) v[b]+=llabs(mat[combo[z]][b]-mat[combo[z+1]][b]); vector<ll> h(width*width); for(int z=0;z<(int)combo.size();z++) for(int p=0;p<width*width;p++) h[p]+=flat[combo[z]][p]; vector<ll> dp=v; for(int step=1;step<pick;step++){ vector<ll> ndp(width,INF); for(int j=1;j<width;j++){ll mn=INF; int base=j*width; for(int i=0;i<j;i++) mn=min(mn, dp[i]+h[base+i]); ndp[j]=v[j]+mn;} dp=ndp;} for(int i=0;i<width;i++) best=min(best,dp[i]); } return best; }
int main(){ios::sync_with_stdio(false); cin.tie(nullptr); int n,m,r,c; if(!(cin>>n>>m>>r>>c)) return 0; vector<vector<ll> > rows(n, vector<ll>(m)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>rows[i][j]; if(comb_count(n,r)<=comb_count(m,c)) cout<<best_score(rows,r,c)<<'\n'; else {vector<vector<ll> > tr(m, vector<ll>(n)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) tr[j][i]=rows[i][j]; cout<<best_score(tr,c,r)<<'\n';} return 0;}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 10:44
# update_at: 2026-10-02 10:44

import sys
from itertools import combinations
from math import comb

INF = 10**18  # 分值远小于它，只用来标记"还没选够列"的无效状态


def best_score(mat: list[list[int]], take: int, pick: int) -> int:
    """枚举第一维的 take 个下标组合，在第二维上选出 pick 个下标，返回最小分值。

    固定第一维组合后，分值恰好拆成两部分：第二维每个位置上的纵向相邻差之和 v，
    以及第二维任意两位置之间横跨所选行的横向差之和 h；第二维上做一次
    "选 pick 个、末位是 j" 的顺序 DP 即可把两部分拼成完整分值。
    """
    width = len(mat[0])
    # 每行压平成 width×width 的 |差| 方阵：加入某行时用 zip 一次性加到 h 上
    flat = [[abs(x - y) for x in row for y in row] for row in mat]  # len(mat) 个方阵

    best = INF
    for combo in combinations(range(len(mat)), take):
        # 纵向：该位置上相邻所选行之间的差之和（子矩阵内这些边必然存在）
        v = [
            sum(abs(mat[p][b] - mat[q][b]) for p, q in zip(combo, combo[1:]))
            for b in range(width)
        ]
        # 横向：第二维 i、j 相邻时，横跨所有所选行的差之和
        h = [0] * (width * width)
        for p in combo:
            h = [x + y for x, y in zip(h, flat[p])]

        dp = v[:]  # 只选 1 个位置：只有纵向代价
        for _ in range(1, pick):
            cur = [INF] * width
            for j in range(1, width):  # 末位是 j，前一位只能取更小的 i
                base = j * width
                cur[j] = v[j] + min(dp[i] + h[base + i] for i in range(j))
            dp = cur
        best = min(best, min(dp))
    return best


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    m = next(data)
    r = next(data)
    c = next(data)
    rows = [[next(data) for _ in range(m)] for _ in range(n)]

    # 枚举组合数更少的一维，另一维留给 DP，两侧取 min(C(n,r), C(m,c))
    if comb(n, r) <= comb(m, c):
        mat, take, pick = rows, r, c
    else:
        mat, take, pick = list(map(list, zip(*rows))), c, r

    print(best_score(mat, take, pick))


if __name__ == "__main__":
    solve()

复杂度

设 $W$ 为做 DP 那一维的长度、$L$ 为被枚举那一维的长度。每个组合内： 预处理 $v$ 为 $O(r \cdot W)$，预处理 $h$ 为 $O(r \cdot W^2)$，DP 为 $O(c \cdot W^2)$，因此总时间复杂度为

即枚举行时是 $\binom{n}{r}(r+c)m^2$，枚举列时是 $\binom{m}{c}(c+r)n^2$，取两者中组合数较小的一侧。最坏 $\binom{16}{8} = 12870$ 个组合、每组合数千次运算，约 $10^7$ 量级， 与标准 C++ 解法同阶。

空间复杂度 $O(nm + L \cdot W^2)$：矩阵 $nm$、被枚举维每行压平的 $|差|$ 方阵 $L \cdot W^2$（v/h/dp 各占 $O(W^2)$，可忽略）， 实测峰值约 15MB，远低于 32MB 限制。

总结

本题的钥匙是把分值按"纵向 / 横向"拆开：固定一维的下标组合后，另一维上 每个位置的纵向代价 $v$ 和每对位置的横向代价 $h$ 都与组合无关，选列问题 随即退化为带顺序约束的一维 DP。$\min\!\big(\binom{n}{r}, \binom{m}{c}\big)$ 的枚举方向选择把最坏组合数压到 12870，使 $n, m \leqslant 16$ 的双重选择 问题在秒级内求解。