POJ 2444 - Partition a Matrix

http://poj.org/problem?id=2444

概要

M * N の非負整数からなる行列が与えられる．

これを水平方向か垂直方向に2回切ることで3つの部分行列に分ける． ただし，このときどの部分行列も1つ以上の要素を持っていなければならない．

3つの部分行列の要素の和をそれぞれ X, Y, Z としたとき，|X-Y| + |Y-Z| + |Z-X| の最小値を答える．

制約

解法

a(0,0) から a(i,j) までの累積和を最初に O(M N) で計算しておけば，どの X, Y, Z も定数時間で求められる．

あとは切り方を全部試して最小値を取るだけ． 切り方は

の6種類．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 inline long long ABS(long long x) { return x >= 0 ? x : -x; }
 6 
 7 int main()
 8 {
 9   int M, N;
10   while (scanf("%d %d", &M, &N) != EOF && M != 0) {
11     static long long a[501][501];
12     for (int i = 0; i <= 500; i++) {
13       a[i][0] = a[0][i] = 0;
14     }
15     for (int i = 1; i <= M; i++) {
16       for (int j = 1; j <= N; j++) {
17         int x;
18         scanf("%d", &x);
19         a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + x;
20       }
21     }
22 
23     long long ans = 1LL<<60;
24     for (int i = 1; i < M; i++) {
25       for (int j = 1; j < N; j++) {
26         {
27           // XY
28           // ZZ
29           long long X = a[i][j];
30           long long Y = a[i][N] - a[i][j];
31           long long Z = a[M][N] - (X + Y);
32           ans = min(ans, ABS(X - Y) + ABS(Y - Z) + ABS(Z - X));
33         }
34         {
35           // XX
36           // YZ
37           long long X = a[i][N];
38           long long Y = a[M][j] - a[i][j];
39           long long Z = a[M][N] - (X + Y);
40           ans = min(ans, ABS(X - Y) + ABS(Y - Z) + ABS(Z - X));
41         }
42         {
43           // XY
44           // XZ
45           long long X = a[M][j];
46           long long Y = a[i][N] - a[i][j];
47           long long Z = a[M][N] - (X + Y);
48           ans = min(ans, ABS(X - Y) + ABS(Y - Z) + ABS(Z - X));
49         }
50         {
51           // XZ
52           // YZ
53           long long X = a[i][j];
54           long long Y = a[M][j] - a[i][j];
55           long long Z = a[M][N] - (X + Y);
56           ans = min(ans, ABS(X - Y) + ABS(Y - Z) + ABS(Z - X));
57         }
58       }
59     }
60     for (int i = 1; i < M; i++) {
61       for (int j = i+1; j < M; j++) {
62         // X
63         // Y
64         // Z
65         long long X = a[i][N];
66         long long Y = a[j][N] - X;
67         long long Z = a[M][N] - (X + Y);
68         ans = min(ans, ABS(X - Y) + ABS(Y - Z) + ABS(Z - X));
69       }
70     }
71     for (int i = 1; i < N; i++) {
72       for (int j = i+1; j < N; j++) {
73         // X Y Z
74         long long X = a[M][i];
75         long long Y = a[M][j] - X;
76         long long Z = a[M][N] - (X + Y);
77         ans = min(ans, ABS(X - Y) + ABS(Y - Z) + ABS(Z - X));
78       }
79     }
80     printf("%lld\n", ans);
81   }
82   return 0;
83 }
poj/2444.cc