蛤玮和他的妹子出海游玩,不小心遭遇了海难,他们醒来之后发现自己到了一座金银岛.岛主非常好心的告诉他们在岛的另一边有船可以送他们回家.
这座岛可以看成n*m的矩阵,蛤玮他们在位置(1,1),而船在位置(n,m).蛤玮发现金银岛遍地都是金子,每个格子里有价值a[i,j]的金子,他和妹子打算在回去的路上带一些走.如果他们路过了位置(i,j),就可以假装系鞋带捡走地上的金子.为了不引起怀疑,他们在走的时候只能往接近码头的方向走,即如果蛤玮现在在(i,j),他只能移动到(i+1,j)或者(i,j+1).为了能拿走更多的金子,蛤玮和妹子决定装作互相不认识,这样他们就可以分开走,从而拿到更多的金子.
蛤玮和他妹子想知道他们最多能拿走多少金子.
注意如果蛤玮和他妹子经过了相同的地方,只能得到一次金子,因为地上的捡完就没有了.
Input
T(1<=T<=10),表示数据组数.
每组数据第一行n,m(1<=n,m<=100),接下来n行,每行m个数,第i行第j列的值a[i,j](1<=a[i,j]<=1000)表示位置(i,j)的金子的价值.
Output
每组数据输出一行,蛤玮和他妹子能拿到的金子总价的最大值.
Sample Input
1 2 2 2 1 1 2
Output for Sample Input
6
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cstdlib> 6 #include <cmath> 7 #include <set> 8 #include <map> 9 #include <vector> 10 using namespace std; 11 12 int a[110][110], dp[110][110][110];//dp[i][j][k]表示同时出发，第一个人走到第i行第j列，第二个人走到底k行，第i+j-k列，因为只能向下或右走，所以每个人的行加列相等 13 int main() 14 { 15 int t, n, m, i, j, k; 16 scanf("%d", &t); 17 while(t--) 18 { 19 scanf("%d %d", &n, &m); 20 for(i = 1; i <= n; i++) 21 for(j = 1; j<= m; j++) 22 scanf("%d", &a[i][j]); 23 int M = 0; 24 memset(dp, 0, sizeof(dp)); 25 for(i = 1; i <= n; i++) 26 { 27 for(j = 1; j <= m; j++) 28 { 29 for(k = 1; k <= min(i + j , n); k++)//注意第二个人的行数要小于等于n 30 { 31 if(i + j - k <= m)//注意第二个人的列数要小于等于m 32 { 33 if(i == k) 34 dp[i][j][k] = max(max(dp[i - 1][j][k -1], dp[i][j - 1][k - 1]), max(dp[i][j - 1][k], dp[i - 1][j][k])) + a[i][j];//如果下一步相等，只加一个数 35 else if(i != k) 36 dp[i][j][k] = max(max(dp[i - 1][j][k -1], dp[i][j - 1][k - 1]), max(dp[i][j - 1][k], dp[i - 1][j][k])) + a[i][j] + a[k][i + j - k];//下一步不相等， 加两个数 37 if(dp[i][j][k] > M) 38 M = dp[i][j][k]; 39 //cout << i << " "<< j << " " << k << " " << dp[i][j][k] << endl; 40 } 41 } 42 } 43 } 44 printf("%d ", M); 45 } 46 return 0; 47 }