跳至正文

1 条题解

  • 0
    @ 2026-10-7 20:23:14

    【本题解由站长编写】

    把来回两条路径看成两条同时从 (1,1) 出发、只能右/下的路径。同步走 k 步后两条路径分别在第 i1、i2 行(列都是 k−行号),f[k][i1][i2] 表示该状态的最大好感度和。转移枚举两条路径各自从上/左来。中间状态禁止 i1==i2(两条路径不能经过同一个人),起点终点除外。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    int m, n;
    vector<vector<int>> a;
    int main() {
        cin >> m >> n;
        a.assign(m, vector<int>(n));
        for (auto &r : a) for (auto &x : r) cin >> x;
        int S = m + n - 2;
        const long long NEG = -1e18;
        vector<vector<vector<long long>>> f(S + 1, vector<vector<long long>>(m, vector<long long>(m, NEG)));
        f[0][0][0] = 0;
        for (int k = 1; k <= S; k++)
            for (int i1 = 0; i1 < m; i1++) {
                int j1 = k - i1;
                if (j1 < 0 || j1 >= n) continue;
                for (int i2 = 0; i2 < m; i2++) {
                    int j2 = k - i2;
                    if (j2 < 0 || j2 >= n) continue;
                    if (i1 == i2 && !(k == S && i1 == m - 1)) continue;
                    long long best = NEG;
                    for (int d1 = 0; d1 < 2; d1++)
                        for (int d2 = 0; d2 < 2; d2++) {
                            int p1 = i1 - d1, p2 = i2 - d2;
                            int q1 = j1 - (1 - d1), q2 = j2 - (1 - d2);
                            if (p1 < 0 || p2 < 0 || q1 < 0 || q2 < 0) continue;
                            if (f[k-1][p1][p2] == NEG) continue;
                            long long v = f[k-1][p1][p2] + a[i1][j1] + a[i2][j2];
                            best = max(best, v);
                        }
                    f[k][i1][i2] = best;
                }
            }
        cout << f[S][m-1][m-1] << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    4255
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者