NOIp2000 검사기 수

N*N이 있는 격자 그래프(N<=10, 우리는 그 중 일부 칸에 정수를 채우고 다른 칸에 숫자 0을 넣는다. 아래 그림과 같다(예시 참조): 어떤 사람은 그림의 왼쪽 상단의 A점에서 출발하여 아래로 걸어갈 수도 있고 오른쪽으로 걸어서 오른쪽 하단의 B점에 도달할 수도 있다.지나가는 길에 그는 네모난 칸의 수를 가져갈 수 있다(가져간 칸은 숫자 0으로 바뀔 것이다).이 사람은 A점에서 B점까지 모두 두 번 걸으며 이런 경로 두 개를 찾아내 얻은 수의 합이 가장 크다.

입력

입력한 첫 번째 동작은 정수 N(N*N을 나타내는 네모난 그림)이고 그 다음 줄마다 세 개의 정수가 있으며 앞의 두 개는 위치를 나타내고 세 번째 수는 그 위치에 놓인 수입니다.별도의 행 0은 입력이 끝났음을 나타냅니다.

출력

2개의 경로에서 얻은 최대 합계를 나타내는 정수만 출력할 수 있습니다.

샘플 입력

8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21 
5 6 4
6 3 15
7 2 14
0 0 0

샘플 출력

67
이 문제는 이전에 만든 숫자 삼각형과 매우 비슷하지만, 차이점은 그가 이것을 두 번 가야 하기 때문에 그렇게 하려고 하는 것은 틀림없이 틀린 것이다.이때 둘이 같이 갈 수 있을까 하다가 맥스로 옮겼어요.
이 문제는 데이터가 매우 많기 때문에 직접 네 개의 수조를 열거한다.
상태 압축: 한 걸음 한 걸음이 지난번 갑과 을에서 옮겨왔기 때문에 우리는 x1, x2와 한 걸음의 총계 step를 기억할 수 있다. 이렇게 하면 y1, y2의 값을 직접 계산할 수 있다.

#include
#include
#include
#include
#include
#include
#include
#include
#define MAXN 20
#define INF 2147483647
using namespace std;
int a[MAXN][MAXN],N;
int dp[MAXN][MAXN][MAXN][MAXN];
void init(){
    int X,Y,key;
    memset(dp,0,sizeof dp);
    cin >> N;
    for(;;){
        scanf("%d %d %d",&X,&Y,&key);
        a[X][Y] = key;
        if (!X && !Y && !key) break;
    }
}
int main(){
    init();
    for (int i = 1;i<=N;i++)
      for (int j = 1;j<=N;j++)
        for (int k = 1;k<=N;k++)
          for (int l = 1;l<=N;l++)
    {
        int node;
        if (i == k && j == l) node = a[i][j];
        else node = a[i][j] + a[k][l];
        int a = max(dp[i][j-1][k][l-1],dp[i][j-1][k-1][l]);
        int b = max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]);
        dp[i][j][k][l] = max(a,b) + node;
    }
    cout << dp[N][N][N][N];
    return 0;
}