1 //状态dp[k][i][j] 第k步，该步走的是(i,k-i)、(j,k-j)
2 #include <cstdio>
3 #include <cstring>
4 #define N 35
5
6 int a[N][N], dp[2*N][N][N];
7 int max2(int x, int y)
8 {
9 return x > y ? x : y;
10 }
11
12 int main()
13 {
14 int n;
15 while(scanf("%d",&n)!=EOF)
16 {
17 for(int i=0; i<n; i++)
18 for(int j=0; j<n; j++)
19 scanf("%d",&a[i][j]);
20 if(n==1) printf("%d\n",a[0][0]);
21 else if(n==2) printf("%d\n",a[0][0]+a[1][0]+a[0][1]+a[1][1]);
22 else
23 {
24 memset(dp,0, sizeof(dp));
25 dp[1][0][1] = dp[1][1][0] = a[0][0] + a[1][0] + a[0][1];
26 for(int k=2; k<2*n-2; k++)
27 {
28 for(int i=0; i<n; i++)
29 {
30 for(int j=0; j<n; j++)
31 {
32 if(i==j || k-i>n-1 || k-j>n-1) continue;
33 if(i-1>=0 && j-1>=0) dp[k][i][j] = max2(dp[k][i][j], dp[k-1][i-1][j-1]+a[i][k-i]+a[j][k-j]);
34 if(i-1>=0 && k-1-j>=0 && (i-1)!=j) dp[k][i][j] = max2(dp[k][i][j], dp[k-1][i-1][j]+a[i][k-i]+a[j][k-j]);
35 if(k-1-i>=0 && j-1>=0 && i!=(j-1)) dp[k][i][j] = max2(dp[k][i][j], dp[k-1][i][j-1]+a[i][k-i]+a[j][k-j]);
36 if(k-1-i>=0 && k-1-j>=0) dp[k][i][j] = max2(dp[k][i][j], dp[k-1][i][j]+a[i][k-i]+a[j][k-j]);
37 }
38 }
39 }
40 int ans = max2(dp[2*n-3][n-2][n-1], dp[2*n-3][n-1][n-2]) + a[n-1][n-1];
41 printf("%d\n",ans);
42 }
43 }
44 return 0;
45 }
