思路与算法

枚举r行集合；固定行后预计算每列的纵向代价和任意两列相邻代价，再做选c列且保持顺序的最小代价DP。

正确性说明

每种合法子矩阵有唯一的行集合，枚举不遗漏。固定行后总分可分为所选各列纵向代价与相邻选列横向代价，按最后一列和已选列数转移恰好各计一次，取最小得到该行集合最优，再全局取小。

复杂度

O(C(n,r)(rm²+cm²)+2^n)时间、O(cm+m²+n*m)空间，含每组行枚举的代价表与DP初始化。

易错点

上下相邻指所选矩阵中的相邻行，不是原矩阵相邻行；r或c为1时对应方向贡献为0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, r, c;
    cin >> n >> m >> r >> c;
    vector<vector<int>> a(n, vector<int>(m));
    for (auto &row : a)
        for (int &x : row)
            cin >> x;
    int ans = INT_MAX;
    for (int mask = 0; mask < (1 << n); mask++)
        if (__builtin_popcount((unsigned)mask) == r) {
            vector<int> row;
            for (int i = 0; i < n; i++)
                if (mask >> i & 1)
                    row.push_back(i);
            vector<int> v(m);
            vector<vector<int>> h(m, vector<int>(m));
            for (int j = 0; j < m; j++) {
                for (int i = 1; i < r; i++)
                    v[j] += abs(a[row[i]][j] - a[row[i - 1]][j]);
                for (int k = 0; k < j; k++)
                    for (int i : row)
                        h[k][j] += abs(a[i][k] - a[i][j]);
            }
            vector<vector<int>> dp(c + 1, vector<int>(m, 1000000000));
            for (int j = 0; j < m; j++)
                dp[1][j] = v[j];
            for (int k = 2; k <= c; k++)
                for (int j = k - 1; j < m; j++)
                    for (int p = k - 2; p < j; p++)
                        dp[k][j] = min(dp[k][j], dp[k - 1][p] + h[p][j] + v[j]);
            ans = min(ans, *min_element(dp[c].begin(), dp[c].end()));
        }
    cout << ans << "\n";
}