쪽지

Nyoj 61 쪽지 보내기
며칠 전에 무의식중에 다중 프로세스 DP를 보았는데 알고 보니 오랫동안 고민했던 쪽지 문제는 이중 프로세스 DP였다. 몇 편의 큰 소가 이중 프로세스 DP에 관한 글을 찾아보니 아이디어가 생겼다.
쪽지 전송 문제로 말하자면, 사실은 왼쪽 상단에서 오른쪽 하단까지 교차하지 않는 두 개의 경로 (머리와 꼬리를 제외하고) 를 찾아서 경로의 크기를 가장 크게 하는 것이다.경로가 교차할 수 없기 때문에 우리는 두 사람의 위치를 동시에 고려해야 한다. 만약에 두 사람의 위치를 x1, y1, x2, y2로 설정하면 상태 이동 방정식은 다음과 같은 형식으로 쓸 수 있다.
f(x1,y1,x2,y2)=max{f(x1-1,y1,x2-1,y2),f(x1-1,y1,x2,y2-1),f(x1,y1-1,x2-1,y2),f(x1,y1-1,x2,y2-1)}+map[x1][y1]+map[x2][y2] ;(여기서 x1!=x2|||y1!=y2)
일반적인 방법은 시간의 복잡도든 공간의 복잡도든 모두 매우 높기 때문에 최적화해야 한다는 것을 알 수 있다.
두 사람 모두 오른쪽이나 아래로 내려가야 하기 때문에 반드시 x1+y1=x2+y2가 있을 것이다.그럼 x1+y1=k 설정하기;x2+y2=k ; 우리는 상태 f(x1, y1, x2, y2)를 f(k, x1, x2)로 바꿀 수 있기 때문에 1차원이 줄어든다.상태 전환 방정식은 다음과 같이 작성할 수 있습니다.
f(k,x1,x2)=max{f(k-1,x1-1,x2),f(k-1,x1,x2-1),f(k-1,x1,x2),f(k-1,x1-1,x2-1)}+map[x1][k-x1]+map[x2][k-x2] ;(x1!=x2) (네 가지 상태가 어떤지 생각해볼까?)
 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int map[101][101],res[201][101][101];
int max(int a,int b,int c,int d)
{
    int s,t;
    s = a > b ? a : b;
    t = c > d ? c : d;
    return s > t ? s : t;
}
int work(int n,int m)
{
    int k,x1,x2,y1,y2;
    res[2][1][1]=map[1][1];
    for(k=2;k<=n+m;k++)
        for(x1=1;x1<=n;x1++)
            for(x2=1;x2<=n;x2++)
            {
                y1 = k - x1;  y2 = k - x2;
                if(y1 < 0 || y2 < 0 || y1 > m || y2 > m || y1 == y2)
                    continue;
                res[k][x1][x2]=max(res[k-1][x1-1][x2],res[k-1][x1][x2-1],res[k-1][x1-1][x2-1],res[k-1][x1][x2])+map[x1][y1]+map[x2][y2];
            }
    return res[m+n-1][n][n-1]+map[n][m];
}
int main()
{
    int i,j,k,m,n;
    scanf("%d",&n);
    while(n--)
    {
        memset(res,0,sizeof(res));
        scanf("%d %d",&m,&k);
        for(i=1;i<=m;i++)
            for(j=1;j<=k;j++)
                scanf("%d",&map[i][j]);
        printf("%d
",work(m,k));
    }
    return 0;
}