у меня есть 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}
,
Однако сложность этого фрагмента О(N M 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
представляет монеты противника.
Вот O(N * M)
решение.
Давайте исправим нижний ряд (r
). Если максимум для всех строк между r - K
а также r
известна для каждого столбца, эта проблема может быть сведена к известной проблеме максимума скользящего окна. Таким образом, можно вычислить ответ для фиксированной строки в O(M)
время.
Давайте перебираем все строки в порядке возрастания. Для каждого столбца максимум для всех строк между 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
размер).