#5464. 「eJOI2025」网格 题解

问题分析

我们有一个 $N \times M$ 的网格，从 $(0,0)$ 出发到 $(N-1,M-1)$，每次可以向右或向下移动任意正数步。移动收益为 $|A_{x,y} - A_{x',y'}| - C$，求最大总收益。

关键约束：

• $N \cdot M \leq 500,000$
• 只能向右或向下移动
• 收益可能为负

核心观察

1. 移动性质

由于只能向右或向下，最优路径一定是单调的。实际上，我们可以只考虑每次移动一步的情况，因为多步移动可以分解为单步移动。

2. 绝对值处理

收益计算中的绝对值可以分解：

• $|a-b| = \max(a-b, b-a)$
• 因此 $|a-b| - C = \max(a-b-C, b-a-C)$

3. 动态规划状态

设 $dp[i][j]$ 表示到达 $(i,j)$ 的最大收益。

算法思路

基础DP方程

对于每个位置 $(i,j)$：

• 从上方来：$dp[i][j] = \max\limits_{0 \leq k < i} [dp[k][j] + |A[k][j] - A[i][j]| - C]$
• 从左方来：$dp[i][j] = \max\limits_{0 \leq l < j} [dp[i][l] + |A[i][l] - A[i][j]| - C]$

直接实现复杂度 $O(N^2M + NM^2)$ 不可行。

优化策略

将绝对值拆开：

从上方转移：

$$dp[i][j] = \max \begin{cases} \max\limits_{k < i, A[k][j] \geq A[i][j]} [dp[k][j] + A[k][j] - A[i][j] - C] \\ \max\limits_{k < i, A[k][j] < A[i][j]} [dp[k][j] - A[k][j] + A[i][j] - C] \end{cases}$$

从左方转移类似。

这提示我们维护两个数据结构：

• 对于每列 $j$，维护 $\max(dp[k][j] + A[k][j])$ 和 $\max(dp[k][j] - A[k][j])$
• 对于每行 $i$，维护 $\max(dp[i][l] + A[i][l])$ 和 $\max(dp[i][l] - A[i][l])$

高效实现

使用平衡树优化

#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <climits>
using namespace std;

const long long INF = 1e18;

struct ColumnData {
    map<int, long long> max_plus;  // A值 -> max(dp + A)
    map<int, long long> max_minus; // A值 -> max(dp - A)
    
    void update(int A_val, long long dp_val) {
        // 更新max_plus
        long long new_plus = dp_val + A_val;
        if (!max_plus.count(A_val) || new_plus > max_plus[A_val]) {
            max_plus[A_val] = new_plus;
        }
        
        // 更新max_minus
        long long new_minus = dp_val - A_val;
        if (!max_minus.count(A_val) || new_minus > max_minus[A_val]) {
            max_minus[A_val] = new_minus;
        }
    }
    
    long long query_plus(int threshold) {
        // 查询 A[k][j] >= threshold 的最大 (dp[k][j] + A[k][j])
        long long res = -INF;
        auto it = max_plus.lower_bound(threshold);
        while (it != max_plus.end()) {
            res = max(res, it->second);
            ++it;
        }
        return res;
    }
    
    long long query_minus(int threshold) {
        // 查询 A[k][j] < threshold 的最大 (dp[k][j] - A[k][j])
        long long res = -INF;
        auto it = max_minus.lower_bound(threshold);
        if (it != max_minus.begin()) {
            --it;
            while (true) {
                res = max(res, it->second);
                if (it == max_minus.begin()) break;
                --it;
            }
        }
        return res;
    }
};

long long max_profit(int N, int M, int C, vector<vector<int>> A) {
    vector<vector<long long>> dp(N, vector<long long>(M, -INF));
    dp[0][0] = 0;
    
    vector<ColumnData> col_data(M);
    vector<ColumnData> row_data(N);
    
    // 初始化起点
    col_data[0].update(A[0][0], dp[0][0]);
    row_data[0].update(A[0][0], dp[0][0]);
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (i == 0 && j == 0) continue;
            
            long long best = -INF;
            
            // 从上方转移
            if (i > 0) {
                long long case1 = col_data[j].query_plus(A[i][j]);  // A[k][j] >= A[i][j]
                long long case2 = col_data[j].query_minus(A[i][j]); // A[k][j] < A[i][j]
                
                if (case1 > -INF) {
                    best = max(best, case1 - A[i][j] - C);
                }
                if (case2 > -INF) {
                    best = max(best, case2 + A[i][j] - C);
                }
            }
            
            // 从左方转移
            if (j > 0) {
                long long case1 = row_data[i].query_plus(A[i][j]);  // A[i][l] >= A[i][j]
                long long case2 = row_data[i].query_minus(A[i][j]); // A[i][l] < A[i][j]
                
                if (case1 > -INF) {
                    best = max(best, case1 - A[i][j] - C);
                }
                if (case2 > -INF) {
                    best = max(best, case2 + A[i][j] - C);
                }
            }
            
            dp[i][j] = best;
            
            // 更新数据结构
            if (dp[i][j] > -INF) {
                col_data[j].update(A[i][j], dp[i][j]);
                row_data[i].update(A[i][j], dp[i][j]);
            }
        }
    }
    
    return dp[N-1][M-1];
}

复杂度分析

• 时间复杂度：$O(NM \log N)$，每个位置需要 $O(\log N)$ 时间查询和更新平衡树
• 空间复杂度：$O(NM)$，存储 DP 数组和平衡树

。