我有一个 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] .
示例：for 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 MK²） . 我的目标是 reduce 运行时复杂度 . 我已经看过像 this 这样的帖子，但看起来我的"filter"是不可分的，可能是因为sum操作 .
更多信息（ optional ）：这实际上是一种在_529358中开发最优策略的算法，其中：
-
两名球员在
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 代表对手的硬币 .
1 回答
这是一个
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大小的矩形的并集） .