题目大意是一个机器人从1.1出发，要到达m.n点，去的时候只能往右或往上走，回来的时候只能往上或往左走，但是一个点只能走一次，沿途每个点均有宝藏，问最多能拿回宝物的价值是多少。
此问题等价于从1.1出发两个机器人，均要到达m.n点，设两个机器人的速度是一定的，则每一个时刻两个机器人均不能走到相同的格子内，（除了到达m.n的时候）。
若想去的两个机器人不走到同一点，则只需要任意时刻，机器人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])+a[i][k+2-i]+a[j][k+2-j];
如果设1号机器人走的是左边的路线，2号机器人走的是右边的路线，由于路线不想交，所以1号机器人第一步是往下的，而2号机器人是往右的，而到达终点前1号机器人不会达到第n列，同样2号机器人不会到达第m行，然后i和j的取值范围要考虑，必须使得两个的行数均在（1，m)之间，列数均在(1,n)之间，而如果k+1 我们同样可以这样考虑，由于机器人每前进一步，行数和列数有且仅有一个将增加1，所以我们可以考虑k的值代表行数和列数的和，则样比较容易理解，由于到达终点的时候，两条线路必须相交，所以我们可以不让到达终点，即k #include }
参考代码如下；
[cpp]
#include
#include
#define MAX_SIZE 51
using namespace std;
int f[2*MAX_SIZE+10][MAX_SIZE+10][MAX_SIZE+10];
int a[MAX_SIZE+10][MAX_SIZE+10];
int m,n;
int max(int a,int b)
{
if(a>b)
return a;
return b;
}
void execute()
{
if(m==1||n==1)
{
cout<<0<
}
memset(f,0x80,sizeof(f));
int k,i,j;
f[2][1][1]=0;
for(k=3;k
for(i=2;i
if(k-i>=n||k-i<1)
continue;
for(j=1;j
if(i==j)
continue;
if(k-j>n||k-j<=1)
continue;
f[k][i][j]=max(max(f[k-1][i-1][j],f[k-1][i-1][j-1]),max(f[k-1][i][j-1],f[k-1][i][j]));
f[k][i][j]=f[k][i][j]+a[i][k-i]+a[j][k-j];
}
}
}
int ans=f[m+n-1][m][m-1]+a[m][n];
cout<
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>m>>n;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
execute();
}
return 0;
}
#include
#define MAX_SIZE 51
using namespace std;
int f[2*MAX_SIZE+10][MAX_SIZE+10][MAX_SIZE+10];
int a[MAX_SIZE+10][MAX_SIZE+10];
int m,n;
int max(int a,int b)
{
if(a>b)
return a;
return b;
}
void execute()
{
if(m==1||n==1)
{
cout<<0<
}
memset(f,0x80,sizeof(f));
int k,i,j;
f[2][1][1]=0;
for(k=3;k
for(i=2;i
if(k-i>=n||k-i<1)
continue;
for(j=1;j
if(i==j)
continue;
if(k-j>n||k-j<=1)
continue;
f[k][i][j]=max(max(f[k-1][i-1][j],f[k-1][i-1][j-1]),max(f[k-1][i][j-1],f[k-1][i][j]));
f[k][i][j]=f[k][i][j]+a[i][k-i]+a[j][k-j];
}
}
}
int ans=f[m+n-1][m][m-1]+a[m][n];
cout<
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>m>>n;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
execute();
}
return 0;
}