题目链接：

题意：从(1, 1)到(n, n)再到(1, 1).

右下到左上只能左， 上；左上到右下只能右，下。

思路：设两个人同时从(1, 1)出发，如果同时到(i, j)，跳过

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 int dp[35][35][35], num[35][35], n; 8 int main() 9 {10     while(~scanf("%d", &n))11     {12         for(int i = 1; i <= n; i++)13             for(int j = 1; j <= n; j++)14                 scanf("%d", &num[i][j]);15         memset(dp, 0, sizeof(dp));16         dp[1][1][1] = num[1][1];17         for(int i = 1; i <= n; i++)18         {19             for(int j = 1; j <= n; j++)20             {21                 for(int k = 1; k < i + j && k <= n; k++)22                 {23                     if(i == n && j == n)24                         dp[i][j][k] = num[n][n] + max(dp[n - 1][n][n], dp[n][n - 1][n - 1]);25                     else if(i == k)26                         continue;27                     else28                     {29                         dp[i][j][k] = num[i][j] + num[k][i + j - k] + max(max(dp[i - 1][j][k - 1], dp[i][j - 1][k - 1]), max(dp[i - 1][j][k], dp[i][j - 1][k]));30                     }31                 }32             }33         }34         printf("%d\n", dp[n][n][n]);35     }36     return 0;37 }