codeforces 213C Relay Race(dp)

제목:
두 사람은 한 사람이 왼쪽 상단에서 한 사람이 오른쪽 상단에서 각각 상대방의 출발점을 향해 걸어간다.n*n의 칸이 있고 칸마다 하나의 점수가 있습니다. 두 사람이 통과하는 점수와 두 사람이 한 칸을 같이 가면 점수는 한 번만 추가할 수 있습니다.
문제 풀이:
처음에 이렇게 하려고 했는데 dp[i][j][k][l]는 첫 번째 사람이 i에 있고 두 번째 사람이 k에 있으면 l가 얻을 수 있는 최대치를 나타낸다.
그러나 메모리가 현저히 부족해서 스크롤 그룹을 사용했지만 여러 가지wa를 사용했다.
대신이 이렇게 하면 dp[i][j][k]는 두 사람이 모두 i보를 걷고 첫 번째 사람은 j행, 두 번째 사람은 k행의 최대 점수와를 나타낸다.이렇게 하면 첫 번째 사람의 열을 계산할 때 i-j+1, 같은 이치로 두 번째는 i-k+1이다.

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int oo=0x3f3f3f3f;
const ll OO=1LL<<61;
const int Mod=1000000007;
const int maxn=300+5;
int dp[maxn<<1][maxn][maxn];
int maze[maxn][maxn];

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&maze[i][j]);
        memset(dp,-0x3f,sizeof dp);
        dp[1][1][1]=maze[1][1];
        for(int i=2;i<=n*2-1;i++)
        {
            for(int j=1;j<=n;j++)
            if(i-j+1>=1&&i-j+1<=n)
            {
                for(int k=1;k<=n;k++)
                if(i-k+1>=1&&i-k+1<=n)
                {
                    int t;
                    if(j!=k) t=maze[j][i-j+1]+maze[k][i-k+1];
                    else t=maze[j][i-j+1];
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]+t);//          
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-1]+t);//          
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+t);//       ，       
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+t);//       ，      
                }
            }
        }
        printf("%d
",dp[n*2-1][n][n]);
    }
    return 0;
}
/**
1
5
2
11 14
16 12
3
25 16 25
12 18 19
11 13 8

*/