-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsubmatrix.cpp
More file actions
98 lines (97 loc) · 1.88 KB
/
Copy pathsubmatrix.cpp
File metadata and controls
98 lines (97 loc) · 1.88 KB
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<limits.h>
#include<queue>
#include<time.h>
#include<stack>
#include<map>
#include<iostream>
#include<string.h>
#include<functional>
//#include"segment tree.h"
//#include<windows.h>
#define range(i, s, e) for (int i = (s); i < int(e); i++)
#define range0(i, e) for (int i = 0; i < int(e); i++)
#define input_int(n) int n;scanf("%d",&n);
#define INF 0x3f3f3f3f
#define INF2 2147483647
using namespace std;
typedef unsigned long long ull;
typedef pair<int, int> P;
struct EDGE {
int to;
int cost;
};
int n, m, r, c;
int matrix[20][20];
int row[20];
int coloum[20];
int w[20];
int v[20][20];
int f[20][20];
int min_ = INF;
void init() {
scanf("%d %d %d %d", &n, &m, &r, &c);
range(a, 1, n + 1) {
range(b, 1, m + 1) {
scanf("%d", &matrix[b][a]);
}
}
}
void dp() {
fill(w, w + 20, 0);
fill(*v, *v + 20 * 20, 0);
fill(*f, *f + 20 * 20, INF);
range(i, 0, 20) {
f[0][i] = 0;
}
for (int a = 1; a <= m; a++) {
int pre = matrix[a][row[1]];
for (int b = 1; b <= r; b++) {
w[a] += abs(matrix[a][row[b]] - pre);
pre = matrix[a][row[b]];
}
}
for (int j = 1; j <= m; j++) {
for (int k = 1; k <= m; k++) {
for (int i = 1; i <= r; i++) {
v[j][k] += abs(matrix[j][row[i]] - matrix[k][row[i]]);
}
}
}
//dpÇ°ÖÃÔËËã
for (int i = 1; i <= c; i++) {//ÒÑÑ¡iÁÐ
for (int j = i; j <= m - (c - i); j++) {
for (int k = i - 1; k < j; k++) {
f[i][j] = min(f[i][j], f[i - 1][k] + w[j] + v[j][k]);
}
}
}
for (int i = c; i <= m; i++) {
min_ = min(min_, f[c][i]);
if (min_ == 11) {
//getchar();
}
}
}
int dfsr(int pos, int dep) {
row[dep] = pos;
if (dep != r) {
for (register int i = pos + 1; i <= n - (r - dep) + 1; i++) {
dfsr(i, dep + 1);
}
}
else {//½øÐÐDP
dp();
}
return 0;
}
int main() {
init();
for (register int i = 1; i <= n - r + 1; i++) {
dfsr(i, 1);
}
printf("%d", min_);
}