2 차원 최대 합계 창에서 효율적인 C/C++ 알고리즘

Question

(K+1)² 창에서 최대 합계 연산을 적용하는 c[N][M] 행렬이 있습니다. 나는 순진한 알고리즘의 복잡성을 줄이기 위해 노력하고 있습니다.

<!-- 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]을 계산하는 것입니다

은 특히, 여기 ++ C에 내 코드입니다.

예 : 대 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 사이의 모든 행에 대한 최대 값이 모든 열에 대해 알려진 경우이 문제는 잘 알려진 슬라이딩 창 최대 문제점으로 줄일 수 있습니다. 따라서 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 크기의 두 직사각형의 합집합입니다).