codeforces 214E-Relay Race

Description

Furik and Rubik take part in a relay race. The race will be set up on a large square with the side of n meters. The given square is split inton?×?n cells (represented as unit squares), each cell has some number.

At the beginning of the race Furik stands in a cell with coordinates (1,?1), and Rubik stands in a cell with coordinates (n,?n). Right after the start Furik runs towards Rubik, besides, if Furik stands at a cell with coordinates (i,?j), then he can move to cell (i?+?1,?j) or (i,?j?+?1). After Furik reaches Rubik, Rubik starts running from cell with coordinates (n,?n) to cell with coordinates (1,?1). If Rubik stands in cell (i,?j), then he can move to cell (i?-?1,?j) or (i,?j?-?1). Neither Furik, nor Rubik are allowed to go beyond the boundaries of the field; if a player goes beyond the boundaries, he will be disqualified.

To win the race, Furik and Rubik must earn as many points as possible. The number of points is the sum of numbers from the cells Furik and Rubik visited. Each cell counts only once in the sum.

Print the maximum number of points Furik and Rubik can earn on the relay race.

Input

The first line contains a single integer (1?≤?n?≤?300). The next n lines contain n integers each: the j-th number on the i-th line a_i,?j (?-?1000?≤?a_i,?j?≤?1000) is the number written in the cell with coordinates (i,?j).

Output

On a single line print a single number — the answer to the problem.

Sample Input

1
5

5

2
11 14
16 12

53

3
25 16 25
12 18 19
11 13 8

136

思路：題目的大致意思是兩個人參加Relay Race，首先一個人從（1，1）出發去（n，n），走到（n，n）後另外一個人從（n，n）走到（1，1），然後求兩個人沿途經過的每個格子的數最大和，重復走的格子按一次計算。

明白這道題的意思之後，就想到這是一道dp的題，如果只是單方向的走的話，那麼就會很簡單了，然而是雙方向，這樣就要用到4維的dp，記錄兩個人走到的位置，然而n最大達到300，那麼這樣就會爆空間，看了一下別人的思路，使用3維代替4維，用dp[i][j][k]（i代表走的步數，j代表第一個人所處的行，k代表第二個人所處的行，i-j代表第一個人所處的列，i-k代表第二個人所處的列），那麼兩個人的位置就確定了，而且節省了很多空間。

提醒：千萬不要忘記dp數組的初始化，由於數據中會出現負數，不初始化就會出錯。

代碼：

#include 
#include 
using namespace std;
int a[305][305],dp[610][305][305];
int n;
void chu()
{
    for(int i=1;i<=n+n-1;i++)
	for(int j=0;j<=n;j++)
	for(int k=0;k<=n;k++)
		dp[i][j][k]=-1000000;

}
int main()
{
    while(scanf("%d",&n)!=-1)
    {
        chu();
        for(int i=0;i<=n;i++)
            a[0][i]=-10000;
        for(int i=1;i<=n;i++)
        {
            a[i][0]=-10000;
            for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
        }

         if(n==1)
        {
            printf("%d\n",a[1][1]);
            continue;
        }
     int i,j,k;
     dp[1][1][1]=a[1][1];
     for(i=2;i<=n+n-1;i++)
     {
         for(j=1;j<=n;j++)
         {
             if((i-j+1>=1)&&(i-j+1<=n))
             for(k=1;k<=n;k++)
             {
                 if((i-k+1>=1)&&(i-k+1<=n))
                 {
                 if(j!=k)
                 dp[i][j][k]=max(max(dp[i-1][j][k],dp[i-1][j-1][k]),max(dp[i-1][j][k-1],dp[i-1][j-1][k-1]))+a[j][i-j+1]+a[k][i-k+1];
                 else dp[i][j][k]=max(max(dp[i-1][j][k],dp[i-1][j-1][k]),max(dp[i-1][j][k-1],dp[i-1][j-1][k-1]))+a[j][i-j+1];
                 //printf("i=%d j=%d k=%d dp=%d\n",i,j,k,dp[i][j][k]);
                 }
             }
         }
     }
      printf("%d\n",dp[n+n-1][n][n]);
    }
    return 0;
}