给出如下定义：
例如，下面左图中选取第2行和第2、4、5列交叉位置的元素得到一个$2 \times 3$的子矩阵如右图所示。
9 3 3 3 9
9 4 8 7 4
1 7 4 6 6
6 8 5 6 9
7 4 5 6 1
的其中一个$2 \times 3$的子矩阵是
4 7 4
8 6 9
相邻的元素：矩阵中的某个元素与其上下左右四个元素（如果存在的话）是相邻的。
矩阵的分值：矩阵中每一对相邻元素之差的绝对值之和。
本题任务：给定一个n行m列的正整数矩阵，请你从这个矩阵中选出一个r行c列的子矩阵，使得这个子矩阵的分值最小，并输出这个分值。
第一行包含用空格隔开的四个整数n, m, r, c，意义如问题描述中所述，每两个整数之间用一个空格隔开。
接下来的n行，每行包含m个用空格隔开的整数，用来表示问题描述中那个n行m列的矩阵。
一个整数，表示满足题目描述的子矩阵的最小分值。
5 5 2 3
9 3 3 3 9
9 4 8 7 4
1 7 4 6 6
6 8 5 6 9
7 4 5 6 1
6
看起来很麻烦，但我们只需要先dfs出行的所有方案，此时我们已经知道在每一列里能选哪些数，我们只需要再dp列即可。
#include <iostream> #include <cstring> #define MAX_N (16 + 5) #define MAX_M (16 + 5) #define abs(x) ((x) >= 0 ? (x) : -(x)) using namespace std; int n, m, r, c; int a[MAX_N][MAX_M]; int t[MAX_N]; int vr[MAX_M], vc[MAX_M][MAX_M]; int dp[MAX_M][MAX_M]; int ans = 0x7f7f7f7f; void DP() { memset(vr, 0, sizeof vr); memset(vc, 0, sizeof vc); memset(dp, 0x7f, sizeof dp); for(register int i = 2; i <= r; ++i) { for(register int j = 1; j <= m; ++j) { vr[j] += abs(a[t[i]][j] - a[t[i - 1]][j]); } } for(register int i = 2; i <= m; ++i) { for(register int j = 1; j < i; ++j) { for(register int k = 1; k <= r; ++k) { vc[i][j] += abs(a[t[k]][i] - a[t[k]][j]); } } } for(register int i = 1; i <= m; ++i) { dp[i][1] = vr[i]; for(register int j = 2; j <= c && j <= i; ++j) { for(register int k = 1; k < i; ++k) { dp[i][j] = min(dp[i][j], dp[k][j - 1] + vr[i] + vc[i][k]); } } } for(register int i = c; i <= m; ++i) { ans = min(ans, dp[i][c]); } return; } void DFS(int x, int cnt) { if(cnt == r) { DP(); return; } for(register int i = x; i + r - cnt - 1 <= n; ++i) { t[cnt + 1] = i; DFS(i + 1, cnt + 1); t[cnt + 1] = 0; } return; } int main() { cin >> n >> m >> r >> c; for(register int i = 1; i <= n; ++i) { for(register int j = 1; j <= m; ++j) { cin >> a[i][j]; } } DFS(1, 0); cout << ans; return 0; }
原文：https://www.cnblogs.com/kcn999/p/11197063.html
