TYVJ1414

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn = 41;
 7 int a[maxn][maxn],dp[maxn+maxn][maxn][maxn][maxn];
 8 int main()
 9 {
10     //freopen("in.txt","r",stdin);
11     int n;
12     while(cin>>n)
13     {
14         for(int i = 1;i<=n;++i)
15             for(int j = 1;j<=n;++j)
16                 scanf("%d",&a[i][j]);
17         memset(dp,0,sizeof(dp));
18         dp[2][1][1][1] = a[1][1];
19         for(int r = 3;r<=n*2;++r)
20             for(int i = 1;i<r;++i)
21                 for(int j = 1;j<r;++j)
22                     for(int k = 1;k<r;++k)
23                     {
24                         int t = max(dp[r-1][i][j][k],max(dp[r-1][i][j-1][k],max(dp[r-1][i][j-1][k-1],dp[r-1][i][j][k-1])));
25                         t = max(t,max(dp[r-1][i-1][j][k],max(dp[r-1][i-1][j][k-1],max(dp[r-1][i-1][j-1][k-1],dp[r-1][i-1][j-1][k]))));
26                         int t1 = a[i][r-i],t2 = a[j][r-j],t3 = a[k][r-k];
27                         t+=a[i][r-i];a[i][r-i] = 0;
28                         t+=a[j][r-j];a[j][r-j] = 0;
29                         t+=a[k][r-k];a[k][r-k] = t3;
30                         a[i][r-i] = t1;a[j][r-j] = t2;
31                         dp[r][i][j][k] = t;
32                     }
33         printf("%d\n",dp[n+n][n][n][n]);
34     }
35 
36     return 0;
37 }