目录

棋盘类 DP （两个人同步走 / 两条路径并行类型）

基本模型

给定一个 n×mn \times m 的网格，每个格子有一个非负整数权值 ai,ja_{i,j}。

有两个人 AA 和 BB 同时 从左上角 (1,1)(1,1) 出发，在每一步中，两个人都必须各自移动一次，移动方式均为：

  • 向右：(x,y)→(x,y+1)(x,y)\to(x,y+1)
  • 向下：(x,y)→(x+1,y)(x,y)\to(x+1,y)

两个人都必须在恰好 n+m−2n+m-2 步后到达右下角 (n,m)(n,m) 。

两个人经过的格子会获得该格子的权值，但如果两个人在同一步走到了 同一个格子 ，该格子的权值只计算一次。

请你求能获得的最大总权值。

输入格式

第一行两个整数 n,mn,m。
接下来 nn 行，每行 mm 个非负整数 ai,ja_{i,j}。

1≤n,m≤601\le n,m\le 60，0≤ai,j≤1090\le a_{i,j}\le 10^9。

输出格式

输出一个整数：最大总权值。

输入输出样例 #1

2 3
1 2 3
4 5 6

21

输入输出样例 #2

3 3
1 100 1
1  1  1
1 100 1

206

解题思路

对于这种类型的问题有一些思维上面的难度，如果只考虑一个人的话，非常的简单，只需要考虑这个人从 (1,1)(1, 1) 走到 (n,m)(n, m) 的 路径最大和 即可。

如果是 搜索 的话直接搜索一遍就可以了。

即便是 DP 解法也很容易思考，直接 $dp_{i, j} = \max(dp_{i - 1, j}, dp_{i, j - 1}) + a_{i, j}$ 即可。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
const LL inf = (1LL << 60);
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
LL a[N][N], Ans;
void dfs(int x, int y, LL Sum) {
    if (x == n && y == m) {
        Ans = max(Ans, Sum);
        return;
    }
    if (x + 1 <= n) dfs(x + 1, y, Sum + a[x + 1][y]);
    if (y + 1 <= m) dfs(x, y + 1, Sum + a[x][y + 1]);
}
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    Ans = -inf;
    dfs(1, 1, a[1][1]); // 起点计入
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
const LL inf = (1LL << 60);
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
LL a[N][N], dp[N][N];
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    for (int i = 0; i <= n; i++) dp[i][0] = -inf;
    for (int j = 0; j <= m; j++) dp[0][j] = -inf;
    dp[1][1] = a[1][1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) continue;
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
        }
    }
    printf("%lld\n", dp[n][m]);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

那么当加上另外一个人其实也不难，无非就是再搜一遍，或者在跑一遍 DP 而已，但是问题在于在 同一步，走到同一格子只计算一次 这个问题如何解决。

首先考虑暴力搜索的方法，在第一个走的时候做一个记录，让第二个人走到第 tt 步的时候知道第一个人在第 tt 步的时候 在哪里即 可，这样第二个人走的时候不过去就行。

通过一个坐标数组记录就行：

  • axtax_t 表示第一个人第 tt 步到达的 xx 坐标。
  • aytay_t 表示第一个人第 tt 步到达的 yy 坐标。
  • SumASumA 表示第一个人走的 所有格子的权值之和 （包含起点终点）。

然后第二个人走的时候如果在同一步走到了同一格子就不算这部分的贡献即可。

最总答案就是第一个人的和加上第二个人的和。

复杂度是 (Tn−1)2\binom{T}{n-1}^2 级别，只能用于很小的 n,mn,m（比如 n,m≤10∼12n,m\le 10\sim 12)。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
const LL inf = (1LL << 60);
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m, T;
LL a[N][N];
int ax[2 * N], ay[2 * N];      // 记录 A 每一步位置（0..T）
LL Ans = -inf;
void dfsB(int x, int y, int step, LL sumA, LL sumB, LL overlap) {
    // 到达 (x,y) 已经是 step 步结束后的状态
    if (x == ax[step] && y == ay[step]) overlap += a[x][y];
    if (step == T) {
        // 必然 x == n && y == m
        LL tot = sumA + sumB - overlap;
        Ans = max(Ans, tot);
        return;
    }
    // B 下一步：下 or 右
    if (x + 1 <= n) dfsB(x + 1, y, step + 1, sumA, sumB + a[x + 1][y], overlap);
    if (y + 1 <= m) dfsB(x, y + 1, step + 1, sumA, sumB + a[x][y + 1], overlap);
}
void dfsA(int x, int y, int step, LL sumA) {
    ax[step] = x;
    ay[step] = y;
    if (step == T) {
        // A 走完，启动 B 的 DFS（从起点开始）
        // B 的 sumB 初始包含起点
        dfsB(1, 1, 0, sumA, a[1][1], 0);
        return;
    }
    // A 下一步：下 or 右
    if (x + 1 <= n) dfsA(x + 1, y, step + 1, sumA + a[x + 1][y]);
    if (y + 1 <= m) dfsA(x, y + 1, step + 1, sumA + a[x][y + 1]);
}
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    T = (n - 1) + (m - 1);
    Ans = -inf;
    // A 从起点开始，sumA 初始包含起点
    dfsA(1, 1, 0, a[1][1]);
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

当前两层 DFS 做的时候本质是：

$$\max_{\text{路径 }A}\ \Big( \text{sum}(A) + \max_{\text{路径 }B}\big(\text{sum}(B)-\text{overlap}(A,B)\big)\Big) $$

其中 overlap(A,B)overlap(A,B) 是 同一步落同格 的那些格子的权值之和（因为 sumA+sumBsumA+sumB 里算了两次，要减回一次）。

首先固定 AA 后，BB 不需要记历史，只需知道 这一步 AA 在哪 即可。

因为同步走到格子 (i,j)(i,j) 的步数是固定的：

t=(i−1)+(j−1)t=(i-1)+(j-1)

因此固定 AA 以后，BB 走到 (i,j)(i,j) 的那一刻，对应的 AA 位置是唯一的 posAtposA_t 。

然后就可以把扣分揉进 格子权值

两层 DFS 里对 BB 的目标是最大化：

sum(B)−overlap(A,B)\text{sum}(B)-\text{overlap}(A,B)

对 BB 的某一步走到 (i,j)(i,j) ，如果它和 AA 在这一步同格，就要减去 ai,ja_{i,j} 。

所以可以定义对 BB 的 有效权值 ：

$$w_{i,j} = \begin{cases} 0, & (i,j)=posA[t]\ \text{其中 }t=(i-1)+(j-1)\\ a_{i,j}, & \text{否则} \end{cases} $$

于是：

$$\text{sum}(B)-\text{overlap}(A,B) = \sum_{(i,j)\in B} w_{i,j} $$

这就变成了 标准单人最大路径和 DP ：

fi,j=max⁡(fi−1,j,fi,j−1)+wi,jf_{i,j}=\max(f_{i-1,j},f_{i,j-1})+w_{i,j}

最后固定 AA 时的最优总分就是：

sum(A)+fn,m\text{sum}(A)+f_{n,m} 
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e2 + 10;
const LL inf = (1LL << 60);
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m, T;
LL a[N][N];
int ax[2 * N], ay[2 * N];      // 记录 A 每一步位置（0..T）
LL Ans = -inf;
LL Bdp() {
    // 构造 B 的有效权值：如果 B 在第 t 步到达的格子恰好等于 A 在第 t 步的位置，则该格子对 B 贡献视作 0
    // 这样 sumB' = sumB - overlap(A,B)
    LL w[N][N];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) w[i][j] = a[i][j];
    // A 的每一步位置 (ax[t], ay[t]) 对应步数 t=(i-1)+(j-1)
    // B 到达同一步同格时，这格对 B 的有效贡献为 0（等价于后面总分里减去重叠）
    for (int t = 0; t <= T; t++) {
        int x = ax[t], y = ay[t];
        w[x][y] = 0;
    }
    LL f[N][N];
    for (int i = 0; i <= n; i++) f[i][0] = -inf;
    for (int j = 0; j <= m; j++) f[0][j] = -inf;
    f[1][1] = w[1][1]; // 注意：若 A 也在 t = 0 的(1, 1)，这里 w[1][1] = 0，正好表示 overlap 的扣除
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) continue;
            f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];
        }
    }
    return f[n][m];
}
void dfsA(int x, int y, int step, LL sumA) {
    ax[step] = x;
    ay[step] = y;
    if (step == T) {
        // 固定 A 后，用 DP 求 B 的最优 sumB' = sumB - overlap
        LL sumBprime = Bdp();
        // 总分 = sumA + sumB - overlap = sumA + (sumB - overlap) = sumA + sumBprime
        Ans = max(Ans, sumA + sumBprime);
        return;
    }
    if (x + 1 <= n) dfsA(x + 1, y, step + 1, sumA + a[x + 1][y]);
    if (y + 1 <= m) dfsA(x, y + 1, step + 1, sumA + a[x][y + 1]);
}
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    T = (n - 1) + (m - 1);
    Ans = -inf;
    // A 从起点开始，sumA 初始包含起点
    dfsA(1, 1, 0, a[1][1]);
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

同步推进

真正的正解思想是：同步推进，把两个人当成一个整体状态，每一步同时决定两个人怎么走。

这就是把 两层 DFS 变成 一层 DP 。

根据上面讲解内容很容易发现 同步推进 的时候就需要表达两个人的状态。

定义（步数隐含在坐标和里）：

$$dp_{x_1,y_1,x_2,y_2} = \text{两人同时走到 }(x_1,y_1)\text{ 和 }(x_2,y_2)\text{ 时的最大收益} $$

同步意味着必须满足：x1+y1=x2+y2x_1+y_1=x_2+y_2 。

两个人每一步都只能来自 上 或 左（对应之前的 下/右 ）：

$$dp_{x_1,y_1,x_2,y_2} = \max \begin{cases} dp_{x_1-1,y_1,x_2-1,y_2}\\ dp_{x_1-1,y_1,x_2,y_2-1}\\ dp_{x_1,y_1-1,x_2-1,y_2}\\ dp_{x_1,y_1-1,x_2,y_2-1} \end{cases} + gain $$

其中

$$gain= \begin{cases} a_{x_1,y_1}, & (x_1,y_1)=(x_2,y_2)\\ a_{x_1,y_1}+a_{x_2,y_2}, & \text{否则} \end{cases} $$

初始化：

dp1,1,1,1=a1,1dp_{1,1,1,1}=a_{1,1}

答案：

dpn,m,n,mdp_{n,m,n,m}

这就是 把两层 DFS 合并 为一个 DP 的形式：不再需要记录 AA 的整条路径，因为 DP 自己在每一步同时考虑两人的位置，并在同一步同格时自动去重。

复杂度不用想，肯定爆炸，而且空间也会爆炸。

记忆化版本

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e2 + 10;
const LL inf = (1LL << 60);
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m, vis[N][N][N][N];
LL a[N][N];
// dp[x1][y1][x2][y2]：两人分别在(x1,y1),(x2,y2)，并且“已经同步走到了当前步数”时，从这里走到终点的最大后续收益
LL dp[N][N][N][N];
LL Ans = -inf;
inline bool ok(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= m;
}
LL dfs(int x1, int y1, int x2, int y2) {
    // 同步合法性：两人走的步数必须相同
    // 从(1, 1)到(x, y)步数 = (x - 1) + (y - 1) => 坐标和 x + y 固定
    if (x1 + y1 != x2 + y2) return -inf;
    if (!ok(x1, y1) || !ok(x2, y2)) return -inf;
    // 走到终点
    if (x1 == n && y1 == m && x2 == n && y2 == m) {
        return 0;
    }
    if (vis[x1][y1][x2][y2]) return dp[x1][y1][x2][y2];
    vis[x1][y1][x2][y2] = 1;
    LL best = -inf;
    // 下一步：每个人 (D 或 R)，共4种
    // A:
    const int dx[2] = {1, 0}; // D, R
    const int dy[2] = {0, 1};
    for (int mv1 = 0; mv1 < 2; mv1++) {
        int nx1 = x1 + dx[mv1], ny1 = y1 + dy[mv1];
        if (!ok(nx1, ny1)) continue;
        for (int mv2 = 0; mv2 < 2; mv2++) {
            int nx2 = x2 + dx[mv2], ny2 = y2 + dy[mv2];
            if (!ok(nx2, ny2)) continue;
            // 同步走：如果一步后两人不在同一层，会被 dfs 内的同步判断挡掉
            LL sub = dfs(nx1, ny1, nx2, ny2);
            if (sub == -inf) continue;
            // 本步两人落点得分（同格只算一次）
            LL gain = a[nx1][ny1];
            if (!(nx1 == nx2 && ny1 == ny2)) gain += a[nx2][ny2];
            best = max(best, gain + sub);
        }
    }
    dp[x1][y1][x2][y2] = best;
    return best;
}
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    Ans = a[1][1] + dfs(1, 1, 1, 1);
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

DP 版本

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 50 + 10;
const LL inf = (1LL << 60);
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
LL a[N][N];
LL dp[N][N][N][N];
inline bool ok(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= m;
}
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    for (int x1 = 1; x1 <= n; x1++) for (int y1 = 1; y1 <= m; y1++) for (int x2 = 1; x2 <= n; x2++) for (int y2 = 1; y2 <= m; y2++) dp[x1][y1][x2][y2] = -inf;
    // 起点：两人都在 (1, 1)，只算一次
    dp[1][1][1][1] = a[1][1];
    // 按 step = x + y 分层填表，保证依赖都在上一层 (s - 1)
    for (int s = 3; s <= n + m; s++) {
        // 四层循环：枚举 (x1, y1, x2, y2)
        for (int x1 = 1; x1 <= n; x1++) {
            for (int y1 = 1; y1 <= m; y1++) {
                if (x1 + y1 != s) continue;
                for (int x2 = 1; x2 <= n; x2++) {
                    for (int y2 = 1; y2 <= m; y2++) {
                        if (x2 + y2 != s) continue;
                        LL best = -inf;
                        // 两人各自从 (上 或 左) 来，共 4 种组合
                        if (ok(x1 - 1, y1) && ok(x2 - 1, y2)) best = max(best, dp[x1 - 1][y1][x2 - 1][y2]);
                        if (ok(x1 - 1, y1) && ok(x2, y2 - 1)) best = max(best, dp[x1 - 1][y1][x2][y2 - 1]);
                        if (ok(x1, y1 - 1) && ok(x2 - 1, y2)) best = max(best, dp[x1][y1 - 1][x2 - 1][y2]);
                        if (ok(x1, y1 - 1) && ok(x2, y2 - 1)) best = max(best, dp[x1][y1 - 1][x2][y2 - 1]);
                        if (best == -inf) continue;
                        // 本步落点得分：同格只算一次
                        LL gain = a[x1][y1];
                        if (!(x1 == x2 && y1 == y2)) gain += a[x2][y2];
                        dp[x1][y1][x2][y2] = best + gain;
                    }
                }
            }
        }
    }
    printf("%lld\n", dp[n][m][n][m]);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

时间压缩（多项式变形）

发现：同步 ⇒⇒ 两个人永远在同一条对角线层

从 (1,1)(1,1) 出发，每走一步（右或下）都会让 x+yx+y 增加 11 。
两个人同步走（每回合都走一步），所以任意时刻他们走的步数相同 ⇒⇒

x1+y1=x2+y2x_1+y_1 = x_2+y_2

也就是说，两人永远处在同一个 stepstep（同一条对角线层）上。

在固定 step=sstep = s 的层上，yy 不再是自由变量。

因为

s=x+y⇒y=s−xs = x + y \quad \Rightarrow \quad y = s - x

所以当枚举了 ss 和 xx，yy 就已经唯一确定了。

  • 对人 1：y1=s−x1y_1 = s - x_1

  • 对人 2：y2=s−x2y_2 = s - x_2

这样就可以把时间复杂度压到 O((n+m)⋅n2)O((n+m)\cdot n^2) 。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 50 + 10;
const LL inf = (1LL << 60);
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
LL a[N][N];
LL dp[N][N][N][N];
inline bool ok(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= m;
}
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    for (int x1 = 1; x1 <= n; x1++) for (int y1 = 1; y1 <= m; y1++) for (int x2 = 1; x2 <= n; x2++) for (int y2 = 1; y2 <= m; y2++) dp[x1][y1][x2][y2] = -inf;
    // 起点：两人都在 (1, 1)，只算一次
    dp[1][1][1][1] = a[1][1];
    // 按 step = x + y 分层，起点 step = 2，终点 step = n + m
    for (int s = 3; s <= n + m; s++) {
        // 合法 (x, y) 需满足 y = s - x 在 [1, m]
        int xl = max(1, s - m);
        int xr = min(n, s - 1);
        for (int x1 = xl; x1 <= xr; x1++) {
            int y1 = s - x1;
            for (int x2 = xl; x2 <= xr; x2++) {
                int y2 = s - x2;
                // 枚举两人的前驱（上 / 左）组合：4 种
                LL best = -inf;
                // A 从上来 (x1 - 1, y1) or 从左来 (x1, y1 - 1)
                // B 同理
                // 前一层是 s-1，所以这些前驱一定满足 (px+py)=s-1
                if (ok(x1 - 1, y1) && ok(x2 - 1, y2)) best = max(best, dp[x1 - 1][y1][x2 - 1][y2]);
                if (ok(x1 - 1, y1) && ok(x2, y2 - 1)) best = max(best, dp[x1 - 1][y1][x2][y2 - 1]);
                if (ok(x1, y1 - 1) && ok(x2 - 1, y2)) best = max(best, dp[x1][y1 - 1][x2 - 1][y2]);
                if (ok(x1, y1 - 1) && ok(x2, y2 - 1)) best = max(best, dp[x1][y1 - 1][x2][y2 - 1]);
                if (best == -inf) continue;
                // 本步落点得分：同格只算一次
                LL gain = a[x1][y1];
                if (!(x1 == x2 && y1 == y2)) gain += a[x2][y2];
                dp[x1][y1][x2][y2] = best + gain;
            }
        }
    }
    printf("%lld\n", dp[n][m][n][m]);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

空间压缩（滚动数组）

既然同步保证都在同一层：

s=x+y⇒y=s−xs=x+y \Rightarrow y=s-x

那么 存 yy 没有意义——只要存 ss 和 xx 就够了。

于是把状态从四维改成三维：

dps,x1,x2dp_{s,x_1,x_2}

其中

y1=s−x1,y2=s−x2y_1=s-x_1,\quad y_2=s-x_2

另外转移时只会从上一层（上一条对角线）来，所以：

$$dp_{s,\cdot,\cdot}\ \text{只依赖}\ dp_{s-1,\cdot,\cdot} $$

因此 ss 这一维也不用全存，直接滚动两层：

  • prex1,x2pre_{x1, x2} 表示上一层
  • curx1,x2cur_{x1, x2} 表示当前层

这样空间可以降到 O(n2)O(n^2) ，时间降到 O((n+m)⋅n2)O((n+m)\cdot n^2)

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e2 + 10;
const LL inf = (1LL << 60);
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
LL a[N][N];
LL pre[N][N], cur[N][N];
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    for (int x1 = 1; x1 <= n; x1++) for (int x2 = 1; x2 <= n; x2++) pre[x1][x2] = -inf;
    pre[1][1] = a[1][1];
    for (int s = 3; s <= n + m; s++) {
        // 清空当前层
        for (int x1 = 1; x1 <= n; x1++) for (int x2 = 1; x2 <= n; x2++) cur[x1][x2] = -inf;
        // 合法 x 范围：y = s-x ∈ [1,m] => x ∈ [s - m, s - 1]
        int xl = max(1, s - m);
        int xr = min(n, s - 1);
        for (int x1 = xl; x1 <= xr; x1++) {
            int y1 = s - x1;
            for (int x2 = xl; x2 <= xr; x2++) {
                int y2 = s - x2;
                LL best = pre[x1][x2];
                if (x1 > 1) best = max(best, pre[x1 - 1][x2]);
                if (x2 > 1) best = max(best, pre[x1][x2 - 1]);
                if (x1 > 1 && x2 > 1) best = max(best, pre[x1 - 1][x2 - 1]);
                if (best == -inf) continue;
                // 本层落点得分：同格只算一次
                LL gain = a[x1][y1];
                if (!(x1 == x2 && y1 == y2)) gain += a[x2][y2];
                cur[x1][x2] = best + gain;
            }
        }
        // 滚动到下一层
        for (int x1 = 1; x1 <= n; x1++) for (int x2 = 1; x2 <= n; x2++) pre[x1][x2] = cur[x1][x2];
    }
    printf("%lld\n", pre[n][n]);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

综上所述

1）同步带来的对角线层思想

每走一步（右 / 下）都会让 x+yx+y 增 11。两人同步 ⇒⇒ 任意时刻：

x1+y1=x2+y2=sx_1+y_1 = x_2+y_2 = s

关注点： 用 step=sstep = s 把时间显式化，所有状态都落在同一层对角线上。

2）坐标压缩：yy 不是自由变量

在固定层 ss 上：

y=s−xy = s - x

关注点： 只需要枚举 xx（行坐标），列坐标由公式算出来并做合法性判断。 这一步直接把 看似四维 变成 三维 。

3）冲突 / 去重规则怎么体现在 gain\text{gain} 上

同步题 90%90\% 的区别都在 同一格怎么计分 ：

  • 同一步同格只算一次$$gain = a[x_1][y_1] + a[x_2][y_2] \quad \text{若同格则减去一次} $$
  • 如果题目改成 格子全程只能拿一次 ，那就不是只看同一步了，会更复杂（后续会讲，可以先思考一下，这里放一个题目 C. Relay Race(https://codeforces.com/problemset/problem/213/C)）。

关注点： 每层只用判断

(x1,y1)=(x2,y2)(x_1,y_1)=(x_2,y_2)

然后决定加一次还是两次。

4）转移永远只有 44 种（每人 22 种）

每人上一层到这一层只有两种来源（上 / 左），两人组合固定就是 44 种：

$$(x_1,x_2)\leftarrow (x_1, x_2), (x_1-1,x_2), (x_1,x_2-1), (x_1-1,x_2-1) $$

关注点： 写对这 44 个前驱 + 边界合法性。

5）复杂度与空间优化的终点形态

  • 有 stepstep：状态量 (n+m)⋅n2(n+m)\cdot n^2
  • 用滚动数组：空间变成 n2n^2

关注点： 只需要 prex1,x2pre_{x1, x2} / curx1,x2cur_{x1, x2} 两层。

4
已通过
0
题解被赞

0 条评论

目前还没有评论...
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  3. 京ICP备2024092232号-2
  4. 京公网安备图标 京公网安备11010802045784号
  5. DAMON THRONE