题解

两条只允许走“下、右”的路径，一条从左上到右下，另一条从右下到左上，且每个同学最多经过一次（起点与终点可以重合）。标准做法是按照“总步数”同步推进两条路径，动态规划两条路径当前所处的行号。

设两条路径已经各走了 $k-2$ 步（包含起点），此时第一条路径在 $(i_1, j_1)$，第二条路径在 $(i_2, j_2)$，则有 $j_1 = k-i_1,\ j_2 = k-i_2$。用 dp[k][i1][i2] 表示走到这一状态时能取得的最大好心值之和。转移只需考虑前一步四种组合：两条路径分别来自左或上。

当前格子的贡献为 val[i1][j1]，若两条路径不在同一格，再额外加上 val[i2][j2]。初始状态为 dp[2][1][1] = val[1][1]，答案是 dp[m+n][m][m]。状态数和转移均为 $\mathcal{O}((m+n)m^2)$，$m,n \le 50$ 足够。

#include <bits/stdc++.h>
using namespace std;

long long dp[105][55][55];
int val[55][55];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    if (!(cin >> m >> n)) return 0;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> val[i][j];
        }
    }
    const long long NEG = -(1LL << 60);
    int maxk = m + n;
    for (int k = 0; k <= maxk; ++k) {
        for (int i1 = 0; i1 <= m; ++i1) {
            for (int i2 = 0; i2 <= m; ++i2) {
                dp[k][i1][i2] = NEG;
            }
        }
    }
    dp[2][1][1] = val[1][1];
    for (int k = 3; k <= maxk; ++k) {
        for (int i1 = 1; i1 <= m; ++i1) {
            int j1 = k - i1;
            if (j1 < 1 || j1 > n) continue;
            for (int i2 = 1; i2 <= m; ++i2) {
                int j2 = k - i2;
                if (j2 < 1 || j2 > n) continue;
                long long best = dp[k - 1][i1][i2];
                best = max(best, dp[k - 1][i1 - 1][i2]);
                best = max(best, dp[k - 1][i1][i2 - 1]);
                best = max(best, dp[k - 1][i1 - 1][i2 - 1]);
                if (best <= NEG / 2) continue;
                long long add = val[i1][j1];
                if (i1 != i2 || j1 != j2) add += val[i2][j2];
                dp[k][i1][i2] = best + add;
            }
        }
    }
    cout << dp[maxk][m][m] << '\n';
    return 0;
}