체크수 (DP)

Problem H:체크 수

Time Limit: 1 Sec  
Memory Limit: 128 MB
Submit: 28  
Solved: 9

Description

N*N 칸이 있고 칸마다 정수나 0이 있다. 가장 왼쪽 상단에서 가장 오른쪽 하단으로 가면 아래와 오른쪽만 두 번 간다. (즉 왼쪽 상단에서 오른쪽 하단으로 두 번 걷는다) 모든 칸의 수를 합쳐서 최대치인 SUM을 구하고 두 번 같은 칸을 통과하면 마지막으로 SUM에서 이 칸의 계수를 한 번만 더한다.
 

Input

첫 줄 N(1 <= N <= 100)
그리고 N 줄, 줄마다 N 개수.N * N 각 칸의 수치를 순서대로 나타냅니다.(0 <= value <= 1000) ;
 

Output

최대 SUM을 내보냅니다.
 

Sample Input

3
1 2 3
0 2 1
1 4 2

Sample Output

15

HINT

 
Hint
Possible Way:
첫 번째 1 -> 2 -> 2 -> 4 -> 2
두 번째 1 -> 2 -> 3 -> 1 -> 2
SUM = 15
 
 
아이디어:
       DP.모두 두 번 걸으면 두 사람이 동시에 기점에서 종점으로 가는 것으로 볼 수 있다.점마다 위나 왼쪽에서 얻을 수 있기 때문에 두 사람이 동시에 가면 네 가지 조합이 있을 수 있다.그러므로 전이 방정식을 얻을 수 있다.
       Dp [ X1 ] [ Y1 ] [ X2 ] [ Y2 ] = max (Dp [ X1 - 1 ] [ Y1 ] [ X2 - 1 ] [ Y2 ] , 
                                                               Dp [ X1 - 1 ] [ Y1 ] [ X2 ] [ Y2 - 1 ] ,
                                                               Dp [ X1 ] [ Y1 - 1 ] [ X2 - 1 ] [ Y2 ] ,
                                                               Dp [ X1 ] [ Y1 - 1 ] [ X2 ] [ Y2 - 1 ] )+ Map [ X1 ] [ Y1 ] + Map [ X2 ] [ Y2 ];
네 개의 순환, 범위가 1~100이면 시간 복잡도 O(n^4)는 TLE를 조성하기 때문에 더욱 최적화해야 한다.k로 걸음 수를 나타내면 전이 방정식은 다음과 같이 바뀔 수 있습니다.
       Dp [ k ] [ X1 ] [ X2 ]  = max (Dp [ k - 1 ] [ X1 - 1 ] [ X2 - 1 ]  , 
                                                    Dp [ k - 1 ] [ X1 - 1 ] [ X2 ]  ,
                                                    Dp [ k - 1 ] [ X1 ] [ X2 - 1 ] ,
                                                    Dp [ k - 1 ] [ X1 ] [ X2 ] ) + Map [ X1 ] [ k - X1 ] + Map [ X2 ] [ k - X2 ];
이렇게 하면 시간의 복잡도가 O(n ^ 3)로 내려가면 TLE가 발생하지 않는다.
 
어떻게 같은 칸을 갈 때 한 번만 추가하는 것을 피할 수 있습니까?
k는 똑같기 때문에 x1==x2일 때 y1=y2가 같은 칸을 걷기 때문에 x1==x2인지 아닌지를 판단하면 두 번을 넣을지 안 넣을지 결정할 수 있다.제목이 같은 점을 통과하지 못하도록 바뀌면 x1==x2시 continue를 사용하면 됩니다.
 
        AC:

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int dp[210][105][105];
int Map[105][105];

int main () {
            int n, sum;
            scanf("%d", &n);
            for (int i = 0; i < n; ++i)
                    for (int j = 0; j < n; ++j)
                            scanf("%d", &Map[i][j]);

            sum = n + n - 2;

            for (int k = 0; k <= sum; ++k) {
                for (int x1 = 0; x1 < n; ++x1) {
                    for (int x2 = 0; x2 < n; ++x2) {

                            int ans = 0;
                            int y1 = k - x1, y2 = k - x2;
                            if (k > 0 && x1 > 0 && x2 > 0)
                                ans = max(ans, dp[k - 1][x1 - 1][x2 - 1]);
                            if (k > 0 && x1 > 0 && y2 > 0)
                                ans = max(ans, dp[k - 1][x1 - 1][x2]);
                            if (k > 0 && y1 > 0 && x2 > 0)
                                ans = max(ans, dp[k - 1][x1][x2 - 1]);
                            if (k > 0 && y1 > 0 && y2 > 0)
                                ans = max(ans, dp[k - 1][x1][x2]);
                            if (y1 < 0 || y2 < 0) continue;

                            dp[k][x1][x2] = ans + Map[x1][y1] +
                                            (x1 == x2 ? 0 : Map[x2][y2]);

                    }
                }
            }

            printf("%d
", dp[sum][n - 1][n - 1]);
        return 0;
}