Vijos 1493 쪽지 전송(DP)

제목 링크
첫 번째 다중 프로세스 DP,Vijos에서 첫 번째 문제는 삼취방격수...그리고 이런 DP를 본 적이 없어요...그리고 가장 웃긴 것은 CF를 할 때 E문제가 그런 문제와 비슷해서 열심히 배우지 못한 것을 후회하고 기초부터 여러 가지 과정을 강의하는 블로거를 보고 이 문제를 풀었다는 것이다.
먼저 O(n^4)의 폭력 해법이다.이 문제는 nm가 모두 50보다 작다.그래서 폭력적인 방법도 지나갔어.
[i][j][k][u]는 첫 번째 사람이 i에 도착하고 j가 두 번째 사람이 k에 도착하는 것을 대표한다. u가 가장 큰 값을 얻는다. 사실 나는 줄곧 의심했던 문제 중 하나가 중복되지 않는 걷는 방법을 어떻게 판단하고 블로그의 처리를 보는가이다. 그렇구나.간단하게 i==k&j==u를 특판하면 max+p[i][j]가 되고, 가짜면 max+p[i][j]+p[k]가 필요합니다.max는 4가지 이전 상태에서 최대치를 얻을 수 있습니다.

 1 #include <stdio.h>

 2 #include <string.h>

 3 int p[51][51],o[51][51][51][51];

 4 int getmax(int a,int b,int c,int d)

 5 {

 6     int max = -1;

 7     if(max < a)

 8     max = a;

 9     if(max < b)

10     max = b;

11     if(max < c)

12     max = c;

13     if(max < d)

14     max = d;

15     return max;

16 }

17 int main()

18 {

19     int i,j,k,u,n,m,max;

20     scanf("%d%d",&n,&m);

21     for(i = 1;i <= n;i ++)

22     {

23         for(j = 1;j <= m;j ++)

24         scanf("%d",&p[i][j]);

25     }

26     for(i = 1;i <= n;i ++)

27     {

28         for(j = 1;j <= m;j ++)

29         {

30             for(k = 1;k <= n;k ++)

31             {

32                 for(u = 1;u <= m;u ++)

33                 {

34                     max = getmax(o[i-1][j][k-1][u],o[i][j-1][k-1][u],o[i-1][j][k][u-1],o[i][j-1][k][u-1]);

35                     if(i == k&&j == u)

36                     o[i][j][k][u] = max + p[i][j];

37                     else

38                     o[i][j][k][u] = max + p[i][j]+p[k][u];

39                 }

40             }

41         }

42     }

43     printf("%d
",o[n][m][n][m]);

44     return 0;

45 }

또 하나의 신기한 방법이 있는데, 압축 상태라고 할 수 있죠.O(n^4)가 O(n^3)로 바뀌면서 CF라는 문제를 푸는 데 이런 방법이 많이 쓰인다.왼쪽 상단에서 한 걸음 한 걸음 층을 계산하면 각 층은 하나의 대각선에 있다는 것을 알 수 있다. 즉, 그들의 화는 서로 같기 때문에 위치는 k층과 x좌표로 바뀔 수 있다. 두 점은 같은 k를 가지고 있기 때문에 상태 이동 방정식은 3차원으로 쓸 수 있다.
[k][i][j]=max(o[k-1][i-1][j],o[k-1][i][j-1],o[k-1][i-1][j-1],o[i][j])+p[k+2-i]+p[j][k+2-i]((2,1)를 1층으로 한다.)이렇게 0ms, 폭력적인 300ms+를 쓰세요.
여러 가지 경계 문제에 주의하세요. 비록 Vijos에서 물을 건너갈 수 있지만 반드시 경계 문제에 주의해야 합니다. 좋은 실현 방법이 없습니다. CF에서 대신의 실현 방법을 살펴보니 매우 간결하다...

 1 #include <stdio.h>

 2 #include <string.h>

 3 int p[51][51],o[121][51][51];

 4 int getmax(int a,int b,int c,int d)

 5 {

 6     int max = -1;

 7     if(max < a)

 8     max = a;

 9     if(max < b)

10     max = b;

11     if(max < c)

12     max = c;

13     if(max < d)

14     max = d;

15     return max;

16 }

17 int main()

18 {

19     int i,j,k,n,m,max;

20     scanf("%d%d",&n,&m);

21     for(i = 1;i <= n;i ++)

22     {

23         for(j = 1;j <= m;j ++)

24         scanf("%d",&p[i][j]);

25     }

26     o[0][1][1] = p[1][1];

27     for(k = 1;k <= n+m-2;k ++)

28     {

29         for(i = 1;i <= k+1&&i <= n;i ++)if(k+2-i<=m)//  

30         {

31             for(j = 1;j <= k+1&&j <= n;j ++)if(k+2-j<=m)//  

32             {

33                 max = getmax(o[k-1][i][j],o[k-1][i][j-1],o[k-1][i-1][j],o[k-1][i-1][j-1]);

34                 if(i == j)

35                 o[k][i][j] = max + p[i][k+2-i];

36                 else

37                 o[k][i][j] = max + p[i][k+2-i] + p[j][k+2-j];

38             }

39         }

40     }

41     printf("%d
",o[n+m-2][n][n]);

42     return 0;

43 }