A13 正经题解

题意分析
在一个m行n列的矩阵中找到一条从$(1,1)$到$(m,n)$的路径和一条从$(m,n)$到$(1,1)$的路径，使得两条路径不相交且路径上的数值之和最大。
关键观察
无论是正向还是反向，都不影响结果，因此题目转化为找两条从$(1,1)$到$(m,n)$的不相交路径。计算两遍极其困难，题目数据范围仅有50，因此可设定第一维为步数，让两条路径同时前进。（注意，代码中的k表示的是步数+1，也可以理解为是经过的点数）同时，我们设定i和j用于表示当前步数下两条路径分别在i行和j行，若k-1步后一条路径在i行，则它一定位于k-i列，因为从数学上看，若只能向右或下方走，从$(1,1)$到$(x,y)$最少要$x+y$步。i和j的遍历覆盖了所有的可能性。再次观察，我们发现，若$i$不变，$k$增加1，则路径列数（即$k-i$）增加1，这就是向右移动，若i跟着增加1，则是向下移动，j同理。因此若将矩阵中的权值储存在mp数组中，我们可列出转移方程：$dp[k][i][j] = max(dp[k][i][j], dp[k-1][i][j], dp[k-1][i-1][j], dp[k-1][i][j-1], dp[k-1][i-1][j-1])+mp[i][k-i]+mp[j][k-j]$
虽然它已经长的有点诡异了，但是仍然有一个细节，我们要特判$i==j$的情况，防止一位同学加两次。可能有人会说题目明确说明了不能让一个同学传两次，但这正是这个问题的难点之一：可以证明，在网格图中，寻找两条不相交路径的最大和问题，等价于寻找两条允许交叉但不会真正"同时使用"同一节点的路径，通过特判 i == j 时只加一次值，实际上达到了"如果路径交叉，就相当于只使用了一次该同学"的效果。前人已经帮我们证明，在网格图中，如果存在两条相交的最优路径，总可以通过路径调整得到两条不相交的路径且和不变。
（如果你仍然不放心，我将在题解底部提供一个彻底防止路径重复和越界的代码，它同样可以达到AC的效果）
AC代码

#include <bits/stdc++.h>
using namespace std;
int mp[51][51];
int dp[101][51][51];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int m, n;
    cin >> m >> n;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin >> mp[i][j];
        }
    }
    for(int k=3;k<=m+n;k++){
        for(int i=1;i<=m&&i<k;i++){
            for(int j=1;j<=m&&j<k;j++){
                int y1 = k-i;
                int y2 = k-j;
                dp[k][i][j] = max(dp[k][i][j], dp[k-1][i][j]);
                dp[k][i][j] = max(dp[k][i][j], dp[k-1][i-1][j]);
                dp[k][i][j] = max(dp[k][i][j], dp[k-1][i][j-1]);
                dp[k][i][j] = max(dp[k][i][j], dp[k-1][i-1][j-1]);
                if(i==j)
                    dp[k][i][j] += mp[i][y1];
                else
                    dp[k][i][j] += mp[i][y1]+mp[j][y2];
                
            }
        }
    }
    
    cout << dp[m+n][m][m];
    return 0;
}

特判重复

#include <bits/stdc++.h>
using namespace std;
int mp[51][51];
int dp[101][51][51];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int m, n;
    cin >> m >> n;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin >> mp[i][j];
        }
    }
    for(int k=3;k<=m+n;k++){
        for(int i=1;i<=m&&i<k;i++){
            for(int j=1;j<=m&&j<k;j++){
                int y1 = k - i;
                int y2 = k - j;
                if(y1<1||y1>n||y2<1||y2>n) continue;
                if(i==j&&k!=m+n){
                    continue;
                }
                dp[k][i][j] = max(dp[k][i][j], dp[k-1][i][j]);
                dp[k][i][j] = max(dp[k][i][j], dp[k-1][i-1][j]);
                dp[k][i][j] = max(dp[k][i][j], dp[k-1][i][j-1]);
                dp[k][i][j] = max(dp[k][i][j], dp[k-1][i-1][j-1]);
                dp[k][i][j] += mp[i][y1]+(i==j?0:mp[j][y2]);
            }
        }
    }
    
    cout << dp[m+n][m][m];
    return 0;
}