探寻宝藏这里写链接内容
题意很清晰啦，一个机器人从（1，1）点出发到（m，n）点，再从（m，n）点回到最初点。我们可以把它看成在（1,1）点同时有两个机器人出发到（m，n）点。
我开始做的是四维的。f[i][j][x][y]表示 : 机器人一在(i,j)，机器人2在(x,y)时所收集的宝藏最多是多少。机器人1从上面(i-1 , j)或者左面(i , j-1)走到(i, j),机器人2从上面（x-1, y）或者左面（x, y-1）走到（x, y）. 所以f[i][j][x][y] = max(f[i-1][j][x-1][y], f[i-1][j][x][y-1], f[i][j-1][x-1][y], f[i][j-1][x][y-1]). 上一状态有四种情况。
这需要四层循环，如果矩阵太大的话就容易超啦。不过我们发现有些细节，这样可以减少一部分无用的循环。注意 : 同一时间两个机器人走的步数是一样的，也就是ｉ＋ｊ＝ ｘ＋ｙ。
#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
int n, m, t, map[55][55], f[55][55][55][55];
int x1[4] = {0,0,1,1}, y1[4] = {1,1,0,0}, x2[4]={0,1,0,1}, y2[4] = {1,0,1,0};
void dp()
{
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
for(int x = 1; x <= i; x++)
{
for(int y = 1; y<= n; y++)
{
// printf("i = %d j = %d x = %d y = %d\n", i, j, x, y);
if(i == x && y == j)continue;//不能到达同一位置
if(i + j != x + y)continue;//同一时间所走的不是是一样的
for(int k = 0; k < 4; k++)
{
int sum = map[i][j] + map[x][y];
f[i][j][x][y] = max(f[i][j][x][y], f[i-x1[k]][j-y1[k]][x-x2[k]][y-y2[k]] + sum);
}
// printf("f[%d][%d][%d][%d] = %d\n", i,j,x,y,f[i][j][x][y]);
}
}
}
}
}
int main()
{
cin >> t;
while(t--)
{
memset(f, 0, sizeof(f));
memset(map, 0, sizeof(map));
scanf("%d%d", &m, &n);
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
scanf("%d", &map[i][j]);
}
dp();
printf("%d\n", f[m][n-1][m-1][n] + map[m][n]);
}
return 0;
}
在网上看见很多人都是用三维数组存的。比较不容易爆内存。
若两个机器人不走到同一点，则只需要任意时刻，机器人1所在的行数不等于机器人2所在的行数。因为速度相同，出发点相同，若某一时刻k时两个机器人到达了同一行，则他们的列数也必然会相同，所以只需要不在同一行即可，
设f[k][i][j]为第k步时1号机器人在i行2号机器人走到j行所收集的最大宝物价值，则f[k][i][j]=max(f[k-1][i-1][j], f[k-1][i][j-1], f[k-1][i][j], f[k-1][i-1][j-1]) + map[i][k+2-i] + map[j][k+2-j];
如果设1号机器人走的是左边的路线，2号机器人走的是右边的路线，由于路线不想交，所以1号机器人第一步是往下的，而2号机器人是往右的，而到达终点前1号机器人不会达到第n列，同样2号机器人不会到达第m行，然后i和j的取值范围要考虑，必须使得两个的行数均在（1，m)之间，列数均在(1,n)之间，而如果k+1小于m时，行数均是小于m的，
我们同样可以这样考虑，由于机器人每前进一步，行数和列数有且仅有一个将增加1，所以我们可以考虑k的值代表行数和列数的和，则样比较容易理解，由于到达终点的时候，两条线路必须相交，所以我们可以不让到达终点，即k小于m+n；状态转移方程就变成了 f[k][i][j] = max(f[k-1][i-1][j], f[k-1][i][j-1], f[k-1][i][j], f[k-1][i-1][j-1])+a[i][k-i]+a[j][k-j];
#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
int n, m, t, map[55][55], f[105][55][55];
int max1(int a, int b, int c, int d)
{
a = max(a, b);
a = max(a, c);
a = max(a, d);
return a;
}
void dp()
{
int step = m + n - 2;
for(int i = 1; i < step; i++)
{
for(int x1 = 1; x1 <= m; x1++)
{
for(int x2 = 1; x2 < x1; x2++)
{
if(x1 == x2)continue;
f[i][x1][x2] = max1(f[i-1][x1][x2], f[i-1][x1-1][x2], f[i-1][x1-1][x2-1],
f[i-1][x1][x2-1]) + map[x1][i-x1+2] + map[x2][i+2-x2];
}
}
}
}
int main()
{
cin >> t;
while(t--)
{
memset(map, 0, sizeof(map));
memset(f, 0, sizeof(f));
scanf("%d%d", &m, &n);
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
scanf("%d", &map[i][j]);
}
dp();
printf("%d\n", f[m+n-3][m][m-1] + map[m][n]);
}
return 0;
}