https://www.acwing.com/problem/content/description/462/ 从矩阵中选一个子矩阵，按题目的计算方法使得权值最小； 先对选行的方法进行状压，这时每个选出来的子矩阵就是一个r*m的矩阵，计算行的前缀和和每两对列的差值和，因为行的选法已经确定，通过前缀和可以把这个矩阵看成一个一维的背包，按01背包的方法跑一边就行
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 20, INF = 1e9; int n, m, r, c; int matrix[N][N]; int f[N][N]; int cw[N], rw[N][N]; int q[N]; int count(int x) { int s = 0; for (int i = 0; i < n; i ++ ) s += x >> i & 1; return s; } int main() { cin >> n >> m >> r >> c; for (int i = 0; i < n; i ++ ) for (int j = 0; j < m; j ++ ) cin >> matrix[i][j]; int res = INF; for (int state = 0; state < 1 << n; state ++ ) if (count(state) == r) { for (int i = 0, j = 0; i < n; i ++ ) if (state >> i & 1) q[j ++ ] = i;//选了的位置 for (int i = 0; i < m; i ++ )//对每一列 { cw[i] = 0; for (int j = 1; j < r; j ++ )//统计选出来的列的每列的上下差 cw[i] += abs(matrix[q[j]][i] - matrix[q[j - 1]][i]); } for (int i = 0; i < m; i ++ )//当前压出来的行的第ij列每一行的差的和 for (int j = i + 1; j < m; j ++ ) { rw[i][j] = 0; for (int k = 0; k < r; k ++ ) rw[i][j] += abs(matrix[q[k]][i] - matrix[q[k]][j]); } for (int i = 0; i < m; i ++ )//背包 { f[i][1] = cw[i];//当前是第i个，选了1个 for (int j = 2; j <= c; j ++ ) { f[i][j] = INF; for (int k = 0; k < i; k ++ ) f[i][j] = min(f[i][j], f[ k][j - 1] + cw[i] + rw[k][i]); } res = min(res, f[i][c]); } } cout << res << endl; return 0; }