「KTSC 2023 R1」地牢题解

问题分析

我们需要找到两条路径的最大价值总和：

• 哲洙：从 $(0,0)$ 到 $(n-1,n-1)$，只能向右或向下
• 英姬：从 $(0,n-1)$ 到 $(n-1,0)$，只能向左或向下

关键难点在于处理路径交叉点的重复计数问题。

算法思路：动态规划 + 路径分离

核心观察

两条路径的交叉点只会被计算一次价值，因此我们需要找到最优的路径组合来最大化总价值。

1. 四方向动态规划预处理

定义四个DP数组

int f[2][N][N], g[2][N][N];  // 四个方向的DP数组

f[0]：从左上到当前的路径最大价值

f[0][1][1] = a[1][1];
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        upd(f[0][i][j], max(f[0][i-1][j], f[0][i][j-1]) + a[i][j]);

f[1]：从右上到当前的路径最大价值

f[1][1][n] = a[1][n];
for (int i = 1; i <= n; ++i)
    for (int j = n; j; --j)
        upd(f[1][i][j], max(f[1][i-1][j], f[1][i][j+1]) + a[i][j]);

g[0]：从当前到右下的路径最大价值

g[0][n][n] = a[n][n];
for (int i = n; i; --i)
    for (int j = n; j; --j)
        upd(g[0][i][j], max(g[0][i+1][j], g[0][i][j+1]) + a[i][j]);

g[1]：从当前到左下的路径最大价值

g[1][n][1] = a[n][1];
for (int i = n; i; --i)
    for (int j = 1; j <= n; ++j)
        upd(g[1][i][j], max(g[1][i+1][j], g[1][i][j-1]) + a[i][j]);

2. 路径交叉点处理策略

情况1：在某个格子交叉

for (int i = 1; i <= n; ++i)
    for (int l = 1; l <= n; ++l) {
        int s = a[i][l];
        s += max(f[0][i-1][l] + g[0][i+1][l] + g[1][i][l-1] + f[1][i][l+1],
                 f[1][i-1][l] + g[1][i+1][l] + f[0][i][l-1] + g[0][i][l+1]);
        upd(ans, s);
    }

路径分离方式：

• 方式A：哲洙从上方来，向右去；英姬从左侧来，向下去
• 方式B：哲洙从左侧来，向下去；英姬从上方来，向左去

情况2：在同一行交叉

for (int i = 1; i <= n; ++i) {
    int lst = -inf;
    for (int r = 1; r <= n; ++r) {
        int vr = max(g[0][i][r] + f[1][i-1][r], f[1][i][r] + g[0][i+1][r]) - a[i][r];
        int vl = max(f[0][i][r] + g[1][i+1][r], g[1][i][r] + f[0][i-1][r]) - a[i][r];
        upd(ans, lst + vr + a[i][r]);
        upd(lst, vl), lst += a[i][r];
    }
}

处理逻辑：

• vr：右侧路径在当前格子的最大价值
• vl：左侧路径在当前格子的最大价值
• 通过遍历找到最优的左右路径分离点

情况3：在同一列交叉

for (int i = 1; i <= n; ++i) {
    int lst = -inf;
    for (int r = 1; r <= n; ++r) {
        int vr = max(g[0][r][i] + g[1][r][i-1], g[0][r][i+1] + g[1][r][i]) - a[r][i];
        int vl = max(f[0][r][i] + f[1][r][i+1], f[0][r][i-1] + f[1][r][i]) - a[r][i];
        upd(ans, lst + vr + a[r][i]);
        upd(lst, vl), lst += a[r][i];
    }
}

处理逻辑：类似行交叉，但在列方向上寻找最优分离点。

代码实现详解

初始化与边界处理

for (int i = 0; i <= n + 1; ++i)
    for (int j = 0; j <= n + 1; ++j)
        f[0][i][j] = f[1][i][j] = g[0][i][j] = g[1][i][j] = -inf;

设置边界为负无穷，避免越界访问。

价值更新函数

void upd(int &x, const int y) {
    x = max(x, y);
}

简洁的最大值更新函数。

数据预处理

for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        a[i][j] = V[i - 1][j - 1];

将0-indexed输入转换为1-indexed内部存储。

算法复杂度分析

• DP预处理：$O(N^2)$，四个方向各一次
• 交叉点枚举：$O(N^2)$，遍历所有可能的交叉点
• 行列扫描：$O(N^2)$，分别扫描每行和每列
• 总复杂度：$O(N^2)$，满足 $N \leq 1000$ 的要求

关键优化技术

$1.$ 四方向DP：预处理所有可能路径方向的最大价值

$2.$ 路径分离：考虑所有可能的交叉和分离方式

$3.$ 滚动优化：在行列扫描中维护前缀最大值

$4.$ 边界处理：正确处理网格边界情况

算法正确性

路径可行性保证

• 哲洙路径：始终满足向右或向下的约束
• 英姬路径：始终满足向左或向下的约束
• 交叉处理：确保每个格子最多被计算一次

最优性保证

通过枚举所有可能的交叉点和分离方式，算法能够找到真正的最优解。

该解法通过多方向动态规划和精细的路径分离策略，高效解决了双路径最大价值问题。