POJ 2078 - Matrix

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

概要

\(n \times n\) の行列 \(A_{i, j}\) が与えられる。 ある \(i\) 番目の行について、任意の数だけ要素を右にずらす操作を SHIFT という。 うまく SHIFT 操作を行って、\(\mbox{max}_{0 \le j < n} \{c_j | c_j = \Sigma_{0 \le i < n} A_{i, j} \}\) を最小化したときの値を答える。

制約

• \(1 \le n \le 7\)
• \(|A_{i, j}| < 10 ^ 4\)

解法

SHIFT のやり方は \(n ^ n \le 7 ^ 7 = 823543\) 通りしかないので、全通り試して最小値をとるだけ。

 1 #include <iostream>
 2 #include <cmath>
 3 #include <vector>
 4 #include <limits>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 int work(const vector<vector<int> >& a)
 9 {
10   const int N = a.size();
11   int m = 0;
12   for (int j = 0; j < N; j++) {
13     int s = 0;
14     for (int i = 0; i < N; i++) {
15       s += a[i][j];
16     }
17     m = max(m, s);
18   }
19   return m;
20 }
21 
22 int solve(vector<vector<int> >& a)
23 {
24   const int N = a.size();
25   const int EN = static_cast<int>(pow(static_cast<double>(N), static_cast<double>(N)));
26   vector<int> steps(N, 0);
27   int ans = numeric_limits<int>::max();
28   ans = min(ans, work(a));
29   for (int s = 1; s < EN; s++) {
30     rotate(a[0].begin(), a[0].begin()+1, a[0].end());
31     ++steps[0];
32     int i = 0;
33     while (steps[i] == N) {
34       steps[i] = 0;
35       ++i;
36       ++steps[i];
37       rotate(a[i].begin(), a[i].begin()+1, a[i].end());
38     }
39     ans = min(ans, work(a));
40   }
41   return ans;
42 }
43 
44 int main()
45 {
46   int n;
47   while (cin >> n && n != -1) {
48     vector<vector<int> > a(n, vector<int>(n));
49     for (int i = 0; i < n; i++) {
50       for (int j = 0; j < n; j++) {
51         cin >> a[i][j];
52       }
53     }
54     cout << solve(a) << endl;
55   }
56   return 0;
57 }