31725 - 포닉스와 달구

step 1

$dp[i][j]$ : i, j 칸을 지날 때 얻을 수 있는 가장 큰 점수

 

이 dp값을 구해봅시다. 이걸 구하기 위해 2개의 dp를 만들겠습니다.

$dp_s[i][j]$ : 시작점에서 i, j까지 올 때 얻을 수 있는 가장 큰 점수

$dp_e[i][j]$ : i, j에서 끝점까지 갈 때 얻을 수 있는 가장 큰 점수

 

$dp_s[i][j] = max ( dp_s[i-1][j], dp_s[i][j-1] )  + A_{i,j}$

$dp_e[i][j] = max ( dp_e[i+1][j], dp_e[i][j+1] )  + A_{i,j}$

로 구할 수 있습니다.

 

그럼 $dp[i][j] = dp_s[i][j]+dp_e[i][j]-A_{i,j}$입니다.

 

$dp[i][j]$는 i, j가 아래 그림의 빨간 칸일 때

 

초록색 영역만 지날 때의 최댓값과 같은 말입니다.

step 2

달구가 빼가는 영역이 정해졌다고 가정해 봅시다. 빨간색이 빼간 영역이라 할 때 포닉스가 얻을 수 있는 최대 점수는

 

dp[파란색 칸] 의 최댓값입니다. 파란 칸을 지나지 않고는 도착할 수 없고 파란 칸을 지난다면 빨간 칸에는 절대 들어갈 수 없습니다.

dp를 2개 더 만들어 봅시다.

$dp_{ld}[i][j] = max(dp[$ 자기 왼쪽 아래에 있는 모든 칸 $])$

$dp_{ru}[i][j] = max(dp[$ 자기 오른쪽 위에 있는 모든 칸 $])$

 

그럼 칸이 정해졌을 때 $max(dp_{ld}[$파란색 칸$], dp_{ru}[$초록색 칸$])$이 포닉스의 점수입니다.

 

모든 사각형에 대해 포닉스가 얻을 수 있는 점수를 구하고 그중 최솟값을 출력하면 됩니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int mapp[2200][2200],mapu[2200][2200],mapd[2200][2200],mapld[2200][2200],mapur[2200][2200];
int main() {
    int n, m, i,j;
    scanf("%d%d", &n, &m);
    for (i = 1;i <= n;i++) {
        for (j = 1;j <= n;j++) {
            scanf("%d", &mapp[i][j]);
            mapu[i][j] = mapp[i][j] + max(mapu[i - 1][j], mapu[i][j - 1]);
        }
    }
    for (i = n;i >= 1;i--) {
        for (j = n;j >= 1;j--) {
            mapd[i][j] = mapp[i][j] + max(mapd[i + 1][j], mapd[i][j + 1]);
            mapp[i][j] = mapu[i][j] + mapd[i][j] - mapp[i][j];
        }
    }
    for (i = 1;i <= n;i++) {
        for (j = 1;j <= n;j++) {
            mapur[i][j] = max(mapp[i][j], mapur[i - 1][j + 1]);
        }
    }
    for (i = n;i >= 1;i--) {
        for (j = n;j >= 1;j--) {
            mapld[i][j] = max(mapp[i][j], mapld[i + 1][j - 1]);
        }
    }
    int minn = 400000000;
    for (i = 1;i <= n - m + 1;i++) {
        for (j = 1;j <= n - m + 1;j++) {
            if (i == 1 && j == 1) continue;
            if (i == n - m + 1 && j == n - m + 1) continue;
            minn = min( minn, max(mapld[i + m][j - 1], mapur[i - 1][j + m]) );
        }
    }
    printf("%d", minn);
    return 0;
}