NOIP2000 검사기 수(동적 계획 상세 해답)

여기는 저희가 일정한 절차에 따라 하겠습니다.

즉 사유 과정을 한 걸음 한 걸음 적어내는 것이다

많은 DP 문제는 이런 생각대로 할 수 있어요.

제목 설명

N∗ N∗ N의 네모 그래프(N<=9 N<=9)가 있으면 우리는 그 중 일부 네모에 정수를 채우고 다른 네모에는 0 0을 넣는다.다음 그림과 같이 예제 참조:

A
 0  0  0  0  0  0  0  0
 0  0 13  0  0  6  0  0
 0  0  0  0  7  0  0  0
 0  0  0 14  0  0  0  0
 0 21  0  0  0  4  0  0
 0  0 15  0  0  0  0  0
 0 14  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
                        B

누군가가 그림의 왼쪽 상단의 A점에서 출발하면 아래로 걸어갈 수도 있고 오른쪽으로 걸어서 오른쪽 하단의 B점에 도달할 수도 있다.지나가는 길에 그는 네모난 칸의 수를 가져갈 수 있다(가져간 칸은 숫자 0으로 바뀔 것이다).이 사람은 A점에서 B점까지 모두 두 번 걸으며 22개의 이런 경로를 찾아내 얻은 수의 합이 가장 크다.입력 출력 형식 입력 형식: 입력의 첫 번째 동작은 정수 N(N N N을 나타내는 사각형 그림)이고 그 다음 줄마다 세 개의 정수가 있으며 앞의 두 개는 위치를 나타내고 세 번째 수는 이 위치에 놓인 수를 나타낸다.별도의 행 0은 입력이 끝났음을 나타냅니다.출력 형식: 두 경로에서 가장 큰 합을 나타내는 정수만 출력합니다.

문제풀이

일반적인 4차원 DP 템플릿두 프로세스를 동시에 시작합니다.

먼저 DFS 쓰기

기왕 제목에서 두 번 가야 한다고 말한 이상 우리는 이 두 경로가 동시에 간다고 가정하자.그러면 우리는 이런 dfs를 쓰기 어렵지 않다.(위조 코드)

int ans,a[][];//a         
void dfs(int x1,int y1,int x2,int y2,int len)
{
    if(          )
    {
        ans=max(ans,len);
        return;
    }
    if(              )
    {
        return;
    }
    int now=len+a[x1+1][y1]+a[x2+1][y2];
    if(x1+1==x2+1&&y1==y2)
    now-=a[x1+1][y1]
    dfs(x1+1,y1,x2+1,y2,now);

    now=len+a[x1][y1+1]+a[x2+1][y2];
    if(x1==x2+1&&y1+1==y2)
    now-=a[x1][y1+1];
    dfs(x1,y1+1,x2+1,y2,now);

    now=len+a[x1+1][y1]+a[x2][y2+1];
    if(x1+1==x2&&y1==y2+1)
    now-=a[x1+1][y1];
    dfs(x1+1,y2,x2,y2+1,now);

    now=len+a[x1][y1+1]+a[x2][y2+1];
    if(x1==x2&&y1+1==y2+1)
    now-=a[x1][y1+1];
    dfs(x1,y1+1,x2,y2+1,now);

}

상태를 설정하다

우리는 dfs가 호출하는 매개 변수에 따라 상태를 설정합니다.만약 k개의 매개 변수가 있다면 일반 k-1개의 매개 변수는 아래 표시를 하고 1개의 매개 변수는 값을 한다.여기는 두 개의 좌표값을 아래로 표시하고 전체 노정을 값으로 한다.즉
f[x1][y1][x2][y2]=len f [ x 1 ] [ y 1 ] [ x 2 ] [ y 2 ] = l e n
경로
x1, y1 x 1, y1, 다른 경로
x2, y2 x 2, y2의 가장 짧은 경로.

기억화 검색으로 쓰기

int a[][];//a         
int dis[][][][];//       -1
int dfs(int x1,int y1,int x2,int y2,int len)
{
    if(              )
    {
        return -INF;
    }
    if(dis[x1][y1][x2][y2]!=-1)
    {
        return dis[x1][y1][x2][y2];
    }
    if(          )
    {
        return len;
    }
    int now=len+a[x1+1][y1]+a[x2+1][y2];
    if(x1+1==x2+1&&y1==y2)
    now-=a[x1+1][y1]
    int t1=dfs(x1+1,y1,x2+1,y2,now);

    now=len+a[x1][y1+1]+a[x2+1][y2];
    if(x1==x2+1&&y1+1==y2)
    now-=a[x1][y1+1];
    int t2=dfs(x1,y1+1,x2+1,y2,now);

    now=len+a[x1+1][y1]+a[x2][y2+1];
    if(x1+1==x2&&y1==y2+1)
    now-=a[x1+1][y1];
    int t3=dfs(x1+1,y2,x2,y2+1,now);

    now=len+a[x1][y1+1]+a[x2][y2+1];
    if(x1==x2&&y1+1==y2+1)
    now-=a[x1][y1+1];
    int t4=dfs(x1,y1+1,x2,y2+1,now);
    return max(t1,max(t2,max(t3,t4)));
}

기억화 개선 순환

네 개의 매개 변수가 있는 이상 4중 순환을 한다.이곳의 검색 순서는 영향을 주지 않는다.그래서 순환 방향은 영향을 주지 않는다.직접 추론하여 해답을 구하다.

int f[][][][];
int a[][];
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++)
{
    f[i][j][k][l]=max()+a[i][j]+a[k][l];
    if(i==k&&j==l)//            。
    f[i][j][k][l]-=a[i][j];
}