c# - 矩阵的左上象限的最大和可以通过反转行和列来形成

Question

我正在研究一个 HackerRank 问题，该问题是在反转行和列后找到 2N x 2N 矩阵左上象限中元素的最大总和。例如，如果矩阵是

M = [
  112  42   83   119
  56   125  56   49
  15   78   101  43
  62   98   114  108
];

那么得到矩阵后，将行和列反转可以形成的最大和是119 + 114 + 56 + 125 = 414

M' = [
   119  114  42   112
   56   125  101  49
   15   78   56   43
   62   98   83   108
];

先反转第 2 列，然后反转第 0 行。

我还没有想出一个简单的解决方案，但我想出了一些可能有用的事实:

• 不可能通过反转行和列来获得任何配置。因此，答案不能是简单地对所有元素进行排序并对它们的前 NxN 求和。
• 此外，不可能将任何 1 元素移动到任何其他位置。例如，位于 (N-1,N-1) 的元素唯一可能移动的位置是 (0,N-1),(N-1,0),(0,0)。
• 从右上象限或左下象限到左上象限需要 1 行反转才能得到元素，从右下象限到左上象限需要 2 次反转才能得到元素。
• 不可能想出一个解决方案来简单地查看左上象限中的每个元素并检查它是否可以被元素范围内可以移动到它的位置的更大元素替换(例如 M[0,1]=42 可以替换为 M[0,2]=83 或 M[3,2]=114 或M[3,1]=98)，因为您还必须考虑在此过程中被拖累的其他元素。

除了这些事实，我想不出任何可以帮助我构建简单解决方案的东西。有什么明显的事实表明我失踪了吗？昨晚我熬夜想着这个。 :)

Answer 1

让我们进一步观察元素 (N - 1, N - 1) 只能在 (0, 0) 中，( N - 1, 0) 或 (0, N - 1) 位置。

• 考虑一个 (r, c) 元素。可以观察到它只能处于以下四个位置之一:(r, c)、(N - r - 1, c)、(r, N - c - 1) 或 (N - 1 - r, N - 1 - c)

• 可以证明总有一个操作序列将位于上述矩形顶点的四个数中最大的数放到左上象限而不改变其余数(证明它, 可以只考虑所有情况并提供一个明确的构造来做到这一点。它很长但很简单，所以我不会在这里发布)。

• 这两个观察给出了以下解决方案:

  int sum = 0;
  for (int i = 0; i < n / 2; i++)
      for (int j = 0; j < n / 2; j++)
          sum += max(a[i][j], a[i][n - j - 1], a[n - i - 1][j], a[n - i - 1][n - j - 1]);