c++ - 二维最大和窗口上的高效 C/C++ 算法

Question

我有一个 c[N][M]我在 (K+1)² 上应用最大和运算的矩阵 window 。我正在尝试降低朴素算法的复杂性。

特别是，这是我的 C++ 代码片段:

<!-- language: cpp -->

int N,M,K;
std::cin >> N >> M >> K;

std::pair< unsigned , unsigned > opt[N][M];
unsigned c[N][M];

// Read values for c[i][j]
// Initialize all opt[i][j] at (0,0).

for ( int i = 0; i < N; i ++ ) {
  for ( int j = 0; j < M ; j ++ ) {

    unsigned max = 0;
    int posX = i, posY = j;

    for ( int ii = i; (ii >= i - K) && (ii >= 0); ii -- ) {
      for ( int jj  = j; (jj >= j - K) && (jj >= 0); jj -- ) {

        // Ignore the (i,j) position
        if (( ii == i ) && ( jj == j )) {
          continue;
        }

        if ( opt[ii][jj].second > max ) {

          max = opt[ii][jj].second;
          posX = ii;
          posY = jj;

        }
      }
    }

    opt[i][j].first  = opt[posX][posY].second;
    opt[i][j].second = c[i][j] + opt[posX][posY].first;

  }
}

算法的目标是计算opt[N-1][M-1] .

示例:N = 4, M = 4, K = 2和:

c[N][M] = 4 1 1 2
          6 1 1 1
          1 2 5 8
          1 1 8 0

...结果应该是opt[N-1][M-1] = {14, 11} .

然而，此代码段的运行复杂度为 O(N M K²)。我的目标是降低运行时的复杂性。我已经看过像 this 这样的帖子了，但似乎我的“过滤器”是不可分离的，可能是因为求和操作。

---

更多信息(可选):这本质上是一种在“游戏”中制定最佳策略的算法，其中:

• 两名球员带领一个团队参加 N × M地牢。
• 地牢的每个位置都有c[i][j]金币。
• 起始位置:(N-1,M-1)其中 c[N-1][M-1] = 0 .
• 事件玩家选择下一个位置将团队移动到位置 (x,y) .
• 下一个位置可以是(x-i, y-j), i <= K, j <= K, i+j > 0中的任何一个.换句话说，它们只能向左和/或向上移动，最多一步 K每个方向。
• 刚刚移动队伍的玩家获得新位置的硬币。
• 主动玩家每回合交替。
• 当团队到达 (0,0) 时游戏结束.
• 双方玩家的最佳策略:如果他们知道对手遵循相同的策略，则最大化自己的金币总和。

因此，opt[i][j].first代表现在将从(i,j)移动的玩家的硬币到另一个位置。 opt[i][j].second代表对方的币。

Answer 1

这是一个O(N * M) 的解决方案。

1. 让我们修复下一行(r)。如果已知 r - K 和 r 之间所有行的每一列的最大值，则此问题可以简化为众所周知的滑动窗口最大值问题。因此可以在 O(M) 时间内计算出固定行的答案。

2. 让我们按升序遍历所有行。对于每一列，r - K 和 r 之间所有行的最大值也是滑动窗口最大值问题。处理所有行的每一列都需要 O(N) 时间。

总时间复杂度是O(N * M)。但是，此解决方案存在一个问题:它不排除 (i, j) 元素。可以通过运行上述算法两次(使用 K * (K + 1) 和 (K + 1) * K 窗口)然后合并结果(一个 (K + 1) * (K + 1) 没有角的正方形是两个矩形的并集 K * (K + 1) 和 (K + 1) * K 大小)。