洛谷：P1725：琪露诺

题目

P1725：琪露诺

分析

这道题目也是明显的单调队列结合DP的题目。其DP的过程相对简单。我们主要讨论其单调队列的实现。

按照单调队列的设定，有两个操作。

位置i的插入

到达某个位置i后，一定有一个对应的“冰冻值”（dp[i]），在插入这个位置后要保持单调队列的单调性。

    void insertIntoQueue(int i) {
    // 弹出队尾dp值不大于当前位置dp值的元素，保持单调性
    while (!monoQueue.empty() && dp[i] >= dp[monoQueue.back()]) {
        monoQueue.pop_back();
    }

    // 将当前位置加入队列
    monoQueue.push_back(i);
}

找到最佳的跳跃位置

参考类似题目（如P01714），在一个可达到的区间范围内，我们只在队首保留了那个最佳位置（由插入操作决定），所以只要获得队首位置即可。

    int queryBestPosition(int x) {
    // 移除队首无法跳到位置x的元素
    while (!monoQueue.empty() && monoQueue.front() + maxJump < x) {
        monoQueue.pop_front();
    }

    // 返回队首元素（dp值最大的位置）
    return monoQueue.front();
}

DP过程

在进行DP的过程中，我们插入的点的位置是最后一个能到达i的那个点的位置（i-minJump），然后找到最好的起跳点。当然，需要判断从i点是否可以跳到终点（i+maxJump>n）。如果是，那么就要更新最大值了。

    for (int i = minJump; i <= n; i++) {
        // 将最后一个能够跳到位置i的点加入队列
        insertIntoQueue(i - minJump);

        // 找到最优的起跳点
        int bestPosition = queryBestPosition(i);

        // 状态转移
        dp[i] = dp[bestPosition] + stones[i];

        // 如果当前位置可以跳到终点之外，更新结果
        if (i + maxJump > n) {
            result = std::max(result, dp[i]);
        }
    }

答案

思考

本题的核心是用单调队列高效维护区间最大值，实现\(O(n)\)的DP转移。这种思想在滑动窗口最大值、最大子段和等问题中也非常常见。