HDU 2686 Matrix

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int dp[80][40][40],val[40][40],n;
 4 int main() {
 5     while(~scanf("%d",&n)) {
 6         memset(dp,0,sizeof dp);
 7         for(int i = 0; i < n; ++i)
 8             for(int j = 0; j < n; ++j)
 9                 scanf("%d",val[i] + j);
10         for(int k = 1; k < 2*n - 2; ++k) {
11             for(int i = 0; i < n; ++i)
12                 for(int j = 0; j < n; ++j) {
13                     if(i == j) continue;
14                     dp[k][i][j] = max(max(dp[k-1][i][j],dp[k-1][i-1][j]),max(dp[k-1][i][j-1],dp[k-1][i-1][j-1]));
15                     dp[k][i][j] += val[i][k - i] + val[j][k - j];
16                 }
17         }
18         int t = 2*n-3;
19         printf("%d\n",max(dp[t][n-1][n-2],dp[t][n-2][n-1]) + val[0][0] + val[n-1][n-1]);
20     }
21     return 0;
22 }