HUT-1673 쪽지 보내기

문제는 두 사람이 각각 왼쪽 상단과 오른쪽 하단에서 서로 쪽지를 전달하지만 문제를 동시에 왼쪽 상단에서 아래로 전달하는 두 쪽지로 전환시켜 서로 교차하지 않는 두 경로의 최대 권한을 구하는 것이다.
TLE가 되었지만 드디어 사유의DP를 이해했다. 항상 노선이 중복될 때 이 dp방정식에 문제가 존재한다고 생각했고 그 후에야 깨달았다. 두 종이 덩어리의 좌표가 같은 점의 dp값은 항상 0이다. 왜냐하면 처음부터 끝까지 업데이트되지 않았기 때문이다.
정의된 dp방정식 f[i][j][k][p]는 1,1이라는 점에서 두 종이 덩어리를 동시에 던지는 구체적인 좌표(i,j)와 (k,p)를 가리킨다. 방정식은 두 점의 동일한 값을 업데이트하지 않는다. 방정식은 다음과 같다.
f[i,j,k,p]:=max{f[i-1,j,k-1,p]                    f[i-1,j,k,p-1]                    f[i,j-1,k-1,p]                     f[i,j-1,k,p-1] 　　　　　　   } + G[i,j] + G[k,p] 
인터넷에 3차원 최적화된...
 
코드는 다음과 같습니다.
 

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <iostream>

#include <algorithm>

#define MAXN 55

using namespace std;

  

int N, M, dp[MAXN][MAXN][MAXN][MAXN];

  

int G[MAXN][MAXN];

  

inline bool judge(int i, int j, int k, int p)

{

    if (i==k && j==p) {

        if (i==N && j==M) {

            return true;

        }

        else

            return false;

    }   

    else

        return true;

}

  

inline int Max(int i, int j, int k, int p)

{

    int mm = dp[i-1][j][k-1][p];

    mm = max(mm, dp[i-1][j][k][p-1]);

    mm = max(mm, dp[i][j-1][k-1][p]);

    mm = max(mm, dp[i][j-1][k][p-1]);

    return mm;

}

  

void DP()

{

    memset(dp, 0, sizeof (dp));

    for (int i = 1; i <= N; ++i) {

        for (int j = 1; j <= M; ++j) {

            for (int k = 1; k <= N; ++k) {

                for (int p = 1; p <= M; ++p) {

                    if (judge(i, j, k, p)) {

                    //  puts("JKLJL");

                        dp[i][j][k][p] = Max(i, j, k ,p) + G[i][j] + G[k][p];

                    }

                }

            }

        }

    }   

    printf("%d
", dp[N][M][N][M]);

}

  

int main()

{ 

    while (scanf("%d %d", &N, &M) == 2) {

        for (int i = 1; i <= N; ++i) {

            for (int j = 1; j <= M; ++j) {

                scanf("%d", &G[i][j]);

            }

        }

        DP();

    } 

}

 
다음은 3차원 DP 사고방식이다. 왼쪽 상단에서 오른쪽 하단까지 유일한 걸음수(step = N+M-2)만 가능하기 때문에 몇 걸음을 걷고 있는 줄 수만 알면 있는 열을 내놓을 수 있기 때문에 상태는 4차원에서 3차원으로 바뀌었다. f[s][i], s는 총 몇 걸음을 걸었는지, i는 첫 번째 쪽지가 있는 줄수, j는 두 번째 쪽지가 있는 줄수를 나타낸다.앞에서 이미 알고 있는 보수와 행수로 열을 얻을 수 있기 때문에 dp방정식과 앞의 것은 차이가 많지 않다.
f[s][i][j] = max {
f[s-1][i][j],//모두 왼쪽에서 전달된 쪽지를 나타낸다
f[s-1][i-1][j],//는 첫 번째 쪽지가 위에서 전달되고 두 번째 쪽지가 왼쪽에서 전달된다는 뜻이다
f[s-1][i][j-1],//첫 번째 쪽지가 왼쪽에서 전달되고, 두 번째 쪽지가 위에서 전달된다는 뜻이다
f[s-1][i-1][j-1]//표시는 모두 위에서 전달된다
}
 
코드는 다음과 같습니다.

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define MAXN 55

using namespace std;

 

int N, M, G[MAXN][MAXN];

int dp[105][MAXN][MAXN];

 

//        ，f[s][i][j] s    ，i           ，j           

 

inline bool judge(int s, int i, int j)

{

    int y1 = s - i + 2;

    int y2 = s - j + 2; //                  

    if (y1 > M || y2 > M || y1 < 1 || y2 < 1) {

        return false;

    }

    if (i == j) {

        if (s == N + M - 2 && i == N) {

            return true;

        }

        else { 

            return false;

        }

    }

    else {

        return true;

    }

}

 

inline int Max(int s, int i, int j)

{

    int mm = dp[s-1][i][j];

    mm = max(mm, dp[s-1][i-1][j]);

    mm = max(mm, dp[s-1][i][j-1]);

    mm = max(mm, dp[s-1][i-1][j-1]);

    return mm;

}

 

void DP()

{

    int step = N + M - 2;

    memset(dp, 0, sizeof (dp));

    dp[0][1][1] = 2 * G[1][1];

    for (int s = 1; s <= step; ++s) { //    step 

        for (int i = 1; i <= N; ++i) {

            for (int j = 1; j <= N; ++j) {

                if (judge(s, i, j)) {

                    dp[s][i][j] = Max(s, i, j)+G[i][s-i+2]+G[j][s-j+2];

                }

            }

        }

    }

    printf("%d
", dp[step][N][N]);

}

 

int main()

{

    while (scanf("%d %d", &N, &M) == 2) {

        for (int i = 1; i <= N; ++i) {

            for (int j = 1; j <= M; ++j) {

                scanf("%d", &G[i][j]);

            }

        }

        DP();

    }

    return 0;

}