칸수 or쪽지 보내기

간단한 검색으로 청북에서 쓴 글을 들었는데 블로그를 안 썼어요. 지금 이 두 문제를 보충하면 사실상 똑같아요. 쪽지 하나는 거꾸로 돌리지만 정착전과 똑같아요. 그래서 똑같은 건 4차원수 그룹으로 두 점의 좌표를 적어요. 두 점 모두 위로 올라가거나 아래로 내려갈 수 있어서 네 가지 상황으로 옮길 수 있어요.바로 내가 아래에 나눈 네 가지 동태전이 방정식은 dp[x][y][x2][y2]=max(dp[x][y-1][x2][y2-1], dp[x-1][y][y][x2][y2-1], dp[x][y-1][y2], dp[x-1][y][y][x2-1][y][y2]])+a[y]+a[x2][y2][y2][x=y&y][x2]이다.

#include
#include 
using namespace std;
int m,n;
int a[55][55];
int dp[55][55][55][55];
int ans=0;
int dfs(int x,int y,int x2,int y2)
{    
    if(x==n&&y==n) {return 0;}
    if(xx][y][x2][y2]=max(dp[x][y][x2][y2],(dp[x+1][y][x2+1][y2]?dp[x+1][y][x2+1][y2]:
    dfs(x+1,y,x2+1,y2))+a[x+1][y]+a[x2+1][y2]-(x+1==x2+1&&y==y2)*a[x+1][y]);
    if(xx][y][x2][y2]=max(dp[x][y][x2][y2],(dp[x+1][y][x2][y2+1]?dp[x+1][y][x2][y2+1]:
    dfs(x+1,y,x2,y2+1))+a[x+1][y]+a[x2][y2+1]-(x+1==x2&&y==y2+1)*a[x+1][y]);
    if(yx][y][x2][y2]=max(dp[x][y][x2][y2],(dp[x][y+1][x2+1][y2]?dp[x][y+1][x2+1][y2]:
    dfs(x,y+1,x2+1,y2))+a[x][y+1]+a[x2+1][y2]-(x==x2+1&&y+1==y2)*a[x][y+1]);
    if(yx][y][x2][y2]=max(dp[x][y][x2][y2],(dp[x][y+1][x2][y2+1]?dp[x][y+1][x2][y2+1]:
    dfs(x,y+1,x2,y2+1))+a[x][y+1]+a[x2][y2+1]-(x==x2&&y+1==y2+1)*a[x][y+1]);
    return dp[x][y][x2][y2];
}
int main()
{
    scanf("%d",&n);int x,y,z;
    while(~scanf("%d%d%d",&x,&y,&z)){
        if(x==0&&y==0&&z==0)
        {
            break;
        }
        a[x][y]=z;
    }

    printf("%d",dfs(1,1,1,1)+a[1][1]);
    return 0;
}

#include
#include 
using namespace std;
int m,n;
int a[55][55];
int dp[55][55][55][55];
int ans=0;
int Max(int x,int y,int z,int w){
    return max(x,max(y,max(z,w)));
}
int main()
{
    scanf("%d",&n);int x,y,z;
    while(~scanf("%d%d%d",&x,&y,&z)){
        if(x==0&&y==0&&z==0)
        {
            break;
        }
        a[x][y]=z;
    }
   for(int x=1;x<=n;x++)
   for(int y=1;y<=n;y++)
   for(int x2=1;x2<=n;x2++)
   for(int y2=1;y2<=n;y2++){
    dp[x][y][x2][y2]=Max(dp[x][y-1][x2][y2-1],dp[x-1][y][x2][y2-1],dp[x][y-1][x2-1][y2],dp[x-1][y][x2-1][y2])+a[x][y]+a[x2][y2]-(x==x2&&y==y2)*a[x][y];
   }
    printf("%d",dp[n][n][n][n]);
    return 0;
}