72 lines
3.1 KiB
C++
72 lines
3.1 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
const int N = 20;
|
||
const int INF = 0x3f3f3f3f;
|
||
|
||
int n, m, r, c; // n行m列的矩阵，从中选择r行c列
|
||
int a[N][N]; // 原始矩阵
|
||
int f[N][N]; // DP数组
|
||
int cw[N]; // 每一列内部的代价，column代价,用cw表示(在行确定的情况下)
|
||
int rw[N][N];
|
||
// 任意两列之间的代价,因为列之间可能不连续，所以需要用二维描述
|
||
// 比如rw[3][6],描述第3列与第6列被选中，它们之间相邻，计算它们之间的差值绝对值，
|
||
// 也就是横向代价。
|
||
|
||
int q[N];
|
||
|
||
// 计算一个二进制数中有多少个数字1
|
||
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 >> a[i][j];
|
||
|
||
int res = INF;
|
||
for (int st = 0; st < 1 << n; st++) // 二进制枚举
|
||
if (count(st) == r) { // 如果二进制的状态表示中，数字1的个数与目标值相同
|
||
for (int i = 0, j = 0; i < n; i++)
|
||
if (st >> i & 1) q[j++] = i; // 记录选择了哪几行
|
||
|
||
// 预处理出每一列(i列)(在选择r行后,形成的小矩阵情况下)
|
||
// 数字上下之间的abs(差值)
|
||
for (int i = 0; i < m; i++) { // 枚举每一列
|
||
cw[i] = 0; // 计算每一列数字上下之间的abs(差值)和
|
||
for (int j = 1; j < r; j++) // 选择的每一行
|
||
cw[i] += abs(a[q[j]][i] - a[q[j - 1]][i]);
|
||
}
|
||
|
||
// 如果i与j列选择后相邻,预处理出sum(abs(差值)),方便DP增量时使用
|
||
// j一定要在i后面才有意义
|
||
for (int i = 0; i < m; i++) // 枚举每一列,开始列
|
||
for (int j = i + 1; j < m; j++) { // 从i列到j列,结束列
|
||
rw[i][j] = 0; // 多轮DP，需要手动初始化后才能进行处理
|
||
for (int k = 0; k < r; k++) // 选择的每一行
|
||
rw[i][j] += abs(a[q[k]][i] - a[q[k]][j]);
|
||
// 将多行的相邻(i,j)列之间的所有abs(差值)都汇总到rw[i][j]
|
||
}
|
||
|
||
// DP
|
||
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;
|
||
// 向前寻找前一个有效位置k
|
||
for (int k = 0; k < i; k++)
|
||
// 两者间的转移关系= + 纵向i列转移代价 + (k,i)之间的横向转移代价
|
||
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;
|
||
} |