题目分析

猴子从任意起点出发，每次只能向右或向上移动到另一个合法点。求路径上香蕉总数的最大值。

核心思路

关键观察：移动规则 (x < x' ∧ y = y') 或 (x = x' ∧ y < y') 意味着路径必须是单调非递减的（在 x 或 y 方向上）。

解法：将问题转化为二维偏序上的最长路径问题。

算法步骤

1. 预处理点集

   • 收集所有合法点 (x, y)
   • 按 x 为第一关键字、y 为第二关键字排序

2. 坐标压缩

   • 对 y 坐标离散化（因为 N 很大但实际出现的 y 值有限）

3. 动态规划 + 数据结构优化

   • 定义 dp[i] 表示到达第 i 个点时的最大香蕉数
   • 对于点 (x, y)，状态转移：

     dp[i] = max{ dp[j] | x[j] ≤ x, y[j] ≤ y } + A[x-1] + B[y-1]
     

   • 使用 Fenwick Tree 维护前缀最大值，支持 O(log N) 查询和更新

4. 答案：所有 dp[i] 中的最大值

复杂度

• 时间复杂度：O(M log N)
• 空间复杂度：O(N + M)

代码框架

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

long long max_bananas(vector<int> A, vector<int> B, vector<pair<int, int>> P) {
    int N = A.size(), M = P.size();
    
    // 1. 坐标压缩
    vector<int> ys;
    for (auto &p : P) ys.push_back(p.second);
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    
    // 2. 排序点集
    sort(P.begin(), P.end());
    
    // 3. Fenwick Tree 维护前缀最大值
    vector<long long> fenw(ys.size() + 2, 0);
    
    long long ans = 0;
    vector<long long> dp(M, 0);
    
    // 4. DP 处理
    for (int i = 0; i < M; i++) {
        int x = P[i].first, y = P[i].second;
        int pos = lower_bound(ys.begin(), ys.end(), y) - ys.begin() + 1;
        
        // 查询前缀最大值
        long long max_val = 0;
        for (int j = pos; j > 0; j -= j & -j)
            max_val = max(max_val, fenw[j]);
        
        dp[i] = max_val + A[x-1] + B[y-1];
        ans = max(ans, dp[i]);
        
        // 更新 Fenwick Tree
        for (int j = pos; j <= ys.size(); j += j & -j)
            fenw[j] = max(fenw[j], dp[i]);
    }
    
    return ans;
}

关键点

• 排序确保处理顺序满足偏序关系
• Fenwick Tree 快速查询二维偏序下的前缀最大值
• 离散化处理稀疏的 y 坐标

这是一个典型的二维偏序 DP问题，通过排序降维后用数据结构优化查询。