使用双线dp，假设两个人同时从左上角移动到右下角，且满足路线不交叉，另k=x1+y1=x2+y2压缩状态进行优化。每次状态转移满足 x1,x2,y1,y2都在矩阵范围内，且(x2,y2)在相对于(x1,y1)右上方的位置。大致如下图。

#include
     
      using namespace std;int n,m;int dp[105][55][55];int mp[55][55];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;        for(int i=1;i<=m;i++)            for(int j=1;j<=n;j++)                cin>>mp[i][j];        memset(dp,0,sizeof(dp));        dp[2][1][1]=0;        for(int k=2;k<=m+n;k++)            for(int x1=1;x1<=n;x1++)                for(int x2=x1+1;x2<=n;x2++)                {                    int y1=k-x1,y2=k-x2;                    if(y1<1 || y2<1 || y1>m || y2>m || y1==y2)                        continue;                    dp[k][x1][x2]=Max(dp[k-1][x1][x2],dp[k-1][x1-1][x2],                                      dp[k-1][x1][x2-1],dp[k-1][x1-1][x2-1])                                      +mp[y1][x1]+mp[y2][x2];                }        printf("%d\n",dp[n+m-1][n-1][n]);    }}