Эффективный алгоритм C/C++ в двумерном окне максимальной суммы

Question

У меня есть c[N][M] матрица, где я применяю операцию с максимальной суммой над (K+1)² окно. Я пытаюсь уменьшить сложность наивного алгоритма.

В частности, вот мой фрагмент кода на 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 (NM K²). Моя цель - уменьшить сложность времени выполнения. Я уже видел подобные сообщения, но, похоже, мой "фильтр" не отделим, возможно, из-за операции суммирования.

---

Дополнительная информация (необязательно): по сути, это алгоритм, который разрабатывает оптимальную стратегию в "игре", где:

• Два игрока возглавляют одну команду в 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 размер).