[codevs2853] 체크 게임 DP

제목 설명Description

메뉴에 네모난 게임이라는 게임을 봤어요~
게임 규칙은 다음과 같습니다.
n*n의 칸 중 1*1의 칸마다 일정 수량의 포인트 보상을 받을 수 있습니다. 왼쪽 상단(1,1), 오른쪽 하단(n,n)을 기록합니다.게임자는 (1,1)부터 (n,n)까지의 경로를 선택하고 경로에서 보상하는 포인트를 획득해야 합니다.경로에 대한 요구도 당연히 있다. 요구는 좌표가 커지는 방향으로만 [(x, y)에서 (x+1, y) 또는 (x, y+1)] 2n-1개 구역을 지나서 (n, n)에 도달하는 것이다.물론 가장 높은 점수를 얻은 사람이 이길 수 있다.
이때 요리는 그의 친구인 달과 달을 보고 그녀를 2인판으로 초대했다.2인판의 규칙은 1인판의 기초 위에서 두 사람의 노선이 같을 수 없다는 것이다.월월이는 요리가 똑똑하다는 것을 알고 너무 비참하게 질까 봐 그와 놀고 싶지 않았다.요리는 당황해서 공평치 D를 정의했다. 이 공평치는 두 사람이 선택한 경로에서 얻을 수 있는 포인트가 일일이 상감하는 차이에 대응하는 절대치의 합이다. 즉, D=sigma(|kxi-kyi|)|(kx,ky는 각각 요리이고 달마다 지나는 모든 구역의 숲계수)이다.하지만 이것은 방대한 계산 임무입니다. 요리가 당신을 찾았습니다. 공평치의 최대치를 계산해 주세요.

설명 입력 Input Description

   ，     n

    n ，  n   ，             

출력 설명 Output Description

공정한 값의 최대값인 정수 Dmax

샘플 Sample Input 입력

4

1 2 3 4

1 5 3 2

8 1 3 4

3 2 1 5

샘플 출력 Sample Output

13

데이터 범위 및 프롬프트 Data Size & Hint

20% 데이터의 경우 0〃n≤20 보장
50% 데이터의 경우 0≥ n≤50 보장
100% 데이터의 경우 0〃n≤100 및 모든 i에 대해 j보증|Kij|≤300
제목의 뜻을 한참 동안 이해하지 못했는데......사실 두 사람이 한 걸음 한 걸음 걸어가는 칸에 대응하는 수의 절대치를 합치면 가장 크다.그리고 중복될 수 없다.더 어렵게 말한 것 같은데... 예시 해석:
(2-1)+(8-3)+(4-1)+(3-2)+(4-1)=13
사실 그 쪽지랑 본질이 똑같아요.하지만 공간은 4차원을 열 수 없다.
사실 두 사람이 어떻게 걷든 걸음걸이가 같으면 출발점인 맨해튼에서 두 사람의 거리는 항상 같다.그래서 우리는 그들이 현재 있는 줄의 수만 기록하고 그들의 가로 좌표의 합을 기록할 수 있다. 그러면 3차원 DP가 되고 마지막에 dp[n][n][2*n]을 출력할 수 있다.
코드:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int size=110;
int num[size][size];

int dp[size][size][size];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
             scanf("%d",&num[i][j]);
        }
    }

    for(int k=2;k<=2*n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(k-1-(j-1)>0&&k-1-(i-1)>0)
                   dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-1]);
                if(k-1-(i-1)>0&&k-1-i>0)
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]);
                if(k-1-(j-1)>0&&k-1-i>0)
                    dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]);
                if(k-1-j>0&&k-1-i>0)
                    dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]);
                if(i!=j&&k-i>0&&k-j>0) 
                    dp[i][j][k]+=abs(num[i][k-i]-num[j][k-j]);
            }
        }
    }

/*
    for(int a=1;a<=n;a++)
    {
        for(int b=1;b<=n;b++)
        {
            for(int c=1;c<=n;c++)
            {
                for(int d=1;d<=n;d++)
                {
                    dp[a][b][c][d]=max(max(dp[a][b-1][c][d-1],dp[a-1][b][c][d-1]),max(dp[a][b-1][c-1][d],dp[a-1][b][c-1][d]));
                    if(a!=c&&b!=d) dp[a][b][c][d]+=abs(num[a][b]-num[c][d]);
                }
            }
        }
    }
*/
    printf("%d
",dp[n][n][2*n]);
//    printf("%d
",dp[n][n][n][n]);
    return 0;
}