使用双线dp，假设两个人同时从左上角移动到右下角，且满足路线不交叉，另k=x1+y1=x2+y2压缩状态进行优化。每次状态转移满足 x1,x2,y1,y2都在矩阵范围内，且(x2,y2)在相对于(x1,y1)右上方的位置。大致如下图。
#include<bits/stdc++.h>
using namespace std;
int n,m;
][][];
][];
int Max(int a,int b,int c,int d)
{
int t1=max(a,b);
int t2=max(c,d);
return max(t1,t2);
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>m>>n;
;i<=m;i++)
;j<=n;j++)
cin>>mp[i][j];
memset(dp,,sizeof(dp));
dp[][][]=;
;k<=m+n;k++)
;x1<=n;x1++)
;x2<=n;x2++)
{
int y1=k-x1,y2=k-x2;
|| y2< || y1>m || y2>m || y1==y2)
continue;
dp[k][x1][x2]=Max(dp[k-][x1][x2],dp[k-][x1-][x2],
dp[k-][x1][x2-],dp[k-][x1-][x2-])
+mp[y1][x1]+mp[y2][x2];
}
printf(][n-][n]);
}
}