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
| #include <bits/stdc++.h>
using namespace std;
int m[101][101], c[101][101];
int C(vector<vector<int>>& x, int& e, int& w, int l, int r) {
if(c[l][r] != -1) return c[l][r];
c[l][r] = 0;
for(int i = 0; i < w; i++) {
int mi = INT_MAX;
for(int j = l; j <= r; j++) {
mi = min(mi, x[j][i]);
}
c[l][r] += mi;
}
return c[l][r];
}
int M(vector<vector<int>>& x, int& e, int& w, int l, int r) {
if(l == r) return 0;
if(m[l][r] != -1) return m[l][r];
m[l][r] = INT_MAX;
for(int i = l; i < r; i++) {
m[l][r] = min(
m[l][r],
M(x,e,w,l,i) + M(x,e,w,i+1,r) + 2 * (C(x,e,w,l,i) + C(x,e,w,i+1,r) - 2 * C(x,e,w,l,r))
);
}
return m[l][r];
}
int solve(int e, int w, vector<vector<int>>& x) {
int res = 0;
memset(m,-1,sizeof(m));
memset(c,-1,sizeof(c));
for(int i = 0; i < w; i++) {
int mi = INT_MAX;
for(int j = 0; j < e; j++)
mi = min(mi, x[j][i]);
res += mi * 2;
for(int j = 0; j < e; j++)
x[j][i] -= mi;
}
return res + M(x,e,w,0,e-1);
}
int main() {
int tc;
cin>>tc;
for(int i = 1; i <= tc; i++) {
int e, w;
cin>>e>>w;
vector<vector<int>> x(e,vector<int>(w));
for(int j = 0; j < e; j++)
for(int k = 0; k < w; k++)
cin>>x[j][k];
cout<<"Case #"<<i<<": "<<solve(e,w,x)<<endl;
}
return 0;
}
|
