CF762D Maximum path 题解

Large_Trouble · 2026-05-10 11:18:41 · 题解

题解背景

题解背景与具体做法无关，是一些做题感言，可以跳过。

依旧在 dmy Y4 上的配套练习题里做到这道 CFer 题。但是感觉只有蓝，随便想想就会了呢？

当然，这仅仅是个人感受，可能是我做类似的套路的题多罢。不过着实想告诉所有人的是：在迷茫中，找到唯一可以确定的方向，才能走向最后的光明。

千年前，笛卡尔如此在一众失败的哲学家中得出了自己的结论；千年后，我们做题，亦当如此。

我能有如此的想法，是因我擅长观察本质、找到可以确定者，而不是有多强。~~刚刚还在吐槽 *2000 的蓝题都做不出来 qwq。~~ 或许拥有天赋的人很少，而我们没有天赋，能做出题目，都在依靠类似的智慧，不过没有发现。

关于题目

题目传送门

good problem!

题目大意

给定一个 3 \times n 的网格，求从 (1, 1) 通过向上下左右移动的方式移动到 (3, n) 的路径的最大的所有经过的点之和。

前置芝士

动态规划原理
前缀和优化 dp
[CSP-J 2020] 方格取数做法

解题思路

首先看到这个题，我们可以瞬间意识到一点：题目肯定不是让我们直接求答案，因为网格图如果上、下、左、右移动而且不重复，肯定得 dfs。

做过 CSP-J 2020 方格取数的同学肯定知道，上、下、右是可行的，而且这题只有三行，转移十分的简单。然后我们看左，这里引发了一个问题：

从 (1,1) 走到 (3,n)，而且总共也就 3 行，十分狭窄，因此导致总体的走向还是向右的。向左走似乎会很容易出现回不来的情况。

具体地：

如果从第一行的起始点开始向左走（之前都是向右、上、下走的），那么肯定要在第二行转弯向左走，并在第三行再次转弯向右走才能继续走向右侧的第 n 列，否则就必须重复经过格子。
如果从第三行的起始点开始向左走（之前都是向右、上、下走的），那么肯定要在第二行转弯向左走，并在第三行再次转弯向右走才能走向第 n 列，否则就必须重复经过格子。
如果从第二行的起始点开始向左走（之前都是向右、上、下走的），那么肯定要在第一、三行转弯并向左走，然后就会由于重复转不回来了。

我们基本上发现向左转只剩下了一个意义：那就是填满一个 3 \times i 的矩阵，然后当 i 为奇数的时候能从第一、三行切换到第三、一行。（因为 i 为偶数的时候似乎只从剩下三个方向走就能满足，只不过这个对做法没有很大的影响）

这个可以在方格取数的做法上加上从前面某列的第三行转化到当前列的第一行，或从前面某列的第一行转化到当前列的第三行的转移就好，可以用前缀和维护。现在 dp 有了最优子结构，可以转移了。

有了如上的观察，可以基本上确定这题的做法：

设 f_{i, j} 表示从 (1, 1) 走到 (j, i) 的路径（没有走到过 i 列之后的格子）的所有格子的最大和。
f_{i, j} = \max(\max_{1 \le k \le 3} f_{i - 1, k} \sum^{\max(j, k)}_{l = \min(j, k)} a_{i, l}, \max_{0 \le k < i} f_{j, i} + \sum^i_{l = j + 1} \sum^3_{o = 1} a_{l, o})
将第二部分使用前缀和优化。

至于前缀和优化怎么处理，请自行查看代码理解，在此不多赘述。

正确代码

# include <cstdio>
# include <cstring>

# define maxn 100010
# define max(x, y) (x > y? x: y)
long long n, a[maxn][3], s[maxn], f[maxn][3], g[maxn][3];

int main( ) {

    scanf("%lld", &n);

    for(long long i = 1; i <= 3; i++)
        for(long long j = 1; j <= n; j++)
            scanf("%lld", &a[j][i - 1]);

    for(long long i = 1; i <= n; i++)
        s[i] = s[i - 1] + a[i][0] + a[i][1] + a[i][2];

    memset(f, -0x3f, sizeof(f));
    memset(g, -0x3f, sizeof(g));
    f[1][0] = a[1][0];
    f[1][1] = a[1][0] + a[1][1];
    f[1][2] = a[1][0] + a[1][1] + a[1][2];
    g[1][0] = max(f[1][0] - s[1], 0);
    g[1][2] = max(f[1][2] - s[1], 0);
    for(long long i = 2; i <= n; i++) {
        f[i][0] = max(f[i][0], f[i - 1][0] + a[i][0]);
        f[i][0] = max(f[i][0], f[i - 1][1] + a[i][0] + a[i][1]);
        f[i][0] = max(f[i][0], f[i - 1][2] + a[i][0] + a[i][1] + a[i][2]);
        f[i][1] = max(f[i][1], f[i - 1][0] + a[i][0] + a[i][1]);
        f[i][1] = max(f[i][1], f[i - 1][1] + a[i][1]);
        f[i][1] = max(f[i][1], f[i - 1][2] + a[i][1] + a[i][2]);
        f[i][2] = max(f[i][2], f[i - 1][0] + a[i][0] + a[i][1] + a[i][2]);
        f[i][2] = max(f[i][2], f[i - 1][1] + a[i][1] + a[i][2]);
        f[i][2] = max(f[i][2], f[i - 1][2] + a[i][2]);
        f[i][0] = max(f[i][0], g[i - 1][2] + s[i]);
        f[i][2] = max(f[i][2], g[i - 1][0] + s[i]);
        g[i][0] = max(g[i - 1][0], f[i][0] - s[i]);
        g[i][2] = max(g[i - 1][2], f[i][2] - s[i]);
    }

    printf("%lld\n", f[n][2]);

    return 0;

}