游戏中的最优路径：动态规划与单调队列的完美结合 - 洛谷P3800题解
一、问题分析
题目描述了一个N行M列的棋盘游戏，灵梦需要从第一行出发，每秒必须下移一行，同时可以在左右方向移动最多T格。目标是收集尽可能多的P点价值。
二、解题思路
状态转移方程：dp[i][j] = max(dp[i-1][k]) + grid[i][j]，其中|k-j| ≤ T
三、关键算法详解
1. 动态规划初始化
// 初始化第一行
for (int j = 1; j <= M; ++j) {
dp[1][j] = grid[1][j];
}第一行的每个位置只能从自身出发，所以初始值就是该位置的P点价值。
2. 单调队列优化
// 正向处理
for (int j = 1; j <= M; ++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] = dp[i-1][dq.front()] + grid[i][j];
}单调队列帮助我们高效维护滑动窗口内的最大值，避免了重复计算。
3. 反向处理
// 反向处理
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]);
}反向处理确保我们考虑了从右侧移动过来的可能性，保证不遗漏任何可能的路径。
四、完整代码
#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;
}原创内容 转载请注明出处
