1 #include 
     
       2 using namespace std; 3 int ans[30][30],dp[60][30][30]; 4 int main() { 5     int n; 6     while(~scanf("%d",&n)) { 7         for(int i=1;i<=n;++i) 8             for(int j=1;j<=n;++j)  9                 scanf("%d",&ans[i][j]);10         memset(dp,0,sizeof(dp));11         dp[0][1][1]=ans[1][1];//一步都没走12         for(int tot=1;tot<=n+n-2;++tot)//走了几步13             for(int i=1;i<=n&&(i-1<=tot);++i)14                 for(int j=1;j<=n&&(j-1<=tot);++j) {15                     dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i-1][j-1]);16                     dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i-1][j]);17                     dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i][j-1]);18                     dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i][j])+ans[i][tot+2-i]+ans[j][tot+2-j];19                     if(i==j) dp[tot][i][j]-=ans[i][tot+2-i];20                 }21         printf("%d\n",dp[n+n-2][n][n]);22     }23     return 0;24 }