当前位置：首页 > 洛谷 > 洛谷P3800题解：动态规划与单调队列优化的高效解法

洛谷P3800题解：动态规划与单调队列优化的高效解法

3个月前 (08-14)

一、题目解读

洛谷P3800题要求在一个N×M的网格中，每个点有能量值，从第一行出发到第N行，每次可向左/右移动不超过T个位置，求路径上能量值总和的最大值。题目核心在于如何高效处理路径限制与能量累积，考验动态规划与优化技巧的应用。

二、解题思路

参考代码采用动态规划+单调队列优化。定义dp[i][j]为从起点到(i,j)位置的最大能量和，利用单调队列维护每一行中“可到达列”的递减能量值序列，确保滑动窗口内始终取到最优前缀。通过双向处理（正向+反向维护队列），兼顾左右移动限制，降低时间复杂度至O(NM)，突破暴力枚举的瓶颈。

三、解题步骤

1. 数据读取与初始化：存储K个特殊点的坐标与能量值，初始化第一行dp值（即直接取网格能量）。

2. 动态规划核心逻辑：

○ 正向处理：维护列j的单调递减队列，确保队首为当前可覆盖范围内（j-T,j）的最大dp值，更新dp[i][j] = 队首值 + 当前网格能量。

○ 反向处理：同理维护队列，覆盖范围变为(j,j+T)，取双向计算结果中的最大值。

3. 结果输出：遍历最后一行dp值，输出最大值。

四、代码与注释

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAX_N = 5005;
const int MAX_M = 5005;

struct Point {
    int x, y, v;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M, K, T;
    cin >> N >> M >> K >> T;
    
    vector<vector<ll>> grid(N+1, vector<ll>(M+1, 0));
    vector<vector<ll>> dp(N+1, vector<ll>(M+1, 0));
    
    // 读取P点数据
    for (int i = 0; i < K; ++i) {
        int x, y, v;
        cin >> x >> y >> v;
        grid[x][y] = v;
    }
    
    // 初始化第一行
    for (int j = 1; j <= M; ++j) {
        dp[1][j] = grid[1][j];
    }
    
    // 动态规划处理每一行
    for (int i = 2; i <= N; ++i) {
        deque<int> dq;
        
        // 处理每一列，使用单调队列优化
        for (int j = 1; j <= M; ++j) {
            // 维护单调队列，保持队列中dp[i-1][k]递减
            while (!dq.empty() && dp[i-1][dq.back()] <= dp[i-1][j]) {
                dq.pop_back();
            }
            dq.push_back(j);
            
            // 移除超出T范围的列
            while (!dq.empty() && dq.front() < j - T) {
                dq.pop_front();
            }
            
            // 计算当前列的最大值
            dp[i][j] = dp[i-1][dq.front()] + grid[i][j];
        }
        
        // 反向处理，考虑从右边移动过来的情况
        dq.clear();
        for (int j = M; j >= 1; --j) {
            while (!dq.empty() && dp[i-1][dq.back()] <= dp[i-1][j]) {
                dq.pop_back();
            }
            dq.push_back(j);
            
            while (!dq.empty() && dq.front() > j + T) {
                dq.pop_front();
            }
            
            // 取两个方向的最大值
            dp[i][j] = max(dp[i][j], dp[i-1][dq.front()] + grid[i][j]);
        }
    }
    
    // 输出最后一行中的最大值
    ll max_power = *max_element(dp[N].begin(), dp[N].end());
    cout << max_power << endl;
    
    return 0;
}