解题思路

题目给定一个$n$×$n$的矩阵，可以对任意行进行任意次数的“SHIFT”操作（每次操作将某行的元素向右循环移动一位）。目标是通过这些操作，使得矩阵中各列元素之和的最大值尽可能小。

关键点：

操作的影响：

每次对第$i$行进行SHIFT操作，相当于将该行的所有元素向右循环移动一位。这意味着每个元素的位置$j$会变为($j$ + $k$) mod $n$，其中k是SHIFT的次数。

目标：

我们需要找到每行SHIFT的次数（即每行循环移动的位数），使得所有列的和的最大值最小。

穷举可能性：

由于$n$的最大值是$7$，每行的SHIFT次数可以是$0$到$n$-$1$（因为移动$n$次相当于不移动），所以总共有$n^n$种可能的组合。对于$n=7$，$7^7$=$823543$，这在现代计算机上是可行的。

计算列和：

对于每一种SHIFT的组合，计算每一列的和，然后找到其中的最大值。最终目标是所有可能组合中最小的最大值。

解题方法

枚举所有可能的SHIFT组合：对于每一行，尝试所有可能的SHIFT次数（$0$到$n-1$），生成所有可能的组合。

计算每种组合的列和：对于每一种组合，计算每一列的和。列$j$的和是所有行$i$的$A[i][(j - shift[i]$) mod $n$]的和。

找到最小的最大列和：在所有组合中，记录最小的最大列和。

C++代码实现：

#include <stdio.h>
#include <algorithm>
 
const int MAXN = 8;
const int INF = 0x3f3f3f3f;
 
int matrix[MAXN][MAXN];
int shift[MAXN];
 
int dfs(int i, int n)
{
  if (i == n) {
    int res = -INF;
    for (int j = 0; j < n; j++) {
      int sum = 0;
      for (int i = 0; i < n; i++)
        sum += matrix[i][(j + shift[i]) % n];
      res = std::max(res, sum);
    }
    return res;
  }
  int res = INF;
  for (shift[i] = 0; shift[i] < n; shift[i]++) {
    res = std::min(res, dfs(i + 1, n));
  }
  return res;
}
 
int main()
{
  int n;
  for (; scanf("%d", &n) == 1, n != -1; ) {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        scanf("%d", &matrix[i][j]);
    printf("%d\n", dfs(1, n));
  }
  return 0;
}