动态规划与优先队列：解决汽车加油行驶问题详解

问题描述

我们有一个N×N的网格，汽车从左上角(1,1)出发，要行驶到右下角(N,N)。汽车装满油后可以行驶K条网格边。在行驶过程中：

1. 行驶规则：
   • 只能沿网格边行驶（上下左右）
   • 向右或向下行驶免费
   • 向左或向上行驶需支付费用B

2. 加油规则：
   • 遇到油库必须加满油，支付费用A
   • 非油库点可选择增设油库，支付费用C（不含加油费A）

3. 目标：找到从起点到终点的最小费用路径

解题思路

这个问题可以用动态规划+优先队列（Dijkstra算法）来解决。我们将汽车的状态定义为：(x坐标, y坐标, 剩余油量)，然后计算到达每个状态的最小费用。

关键点

1. 状态表示：dp[x][y][k]表示在(x,y)位置，剩余油量k时的最小费用
2. 状态转移：
   • 向四个方向移动
   • 根据方向计算费用
   • 处理加油或增设油库的情况
3. 优先队列：确保总是先处理费用最小的状态

优先队列详解

什么是优先队列？

优先队列（Priority Queue）是一种特殊的队列，其中每个元素都有优先级。与普通队列不同，优先队列中的元素不是按照先进先出的顺序出队，而是按照优先级出队。

在C++中，优先队列通过std::priority_queue实现，默认是大顶堆（最大元素优先）。我们可以通过自定义比较器来实现小顶堆（最小元素优先）。

优先队列在本问题中的应用

在本问题中，我们使用优先队列来确保总是先处理当前已知费用最小的状态。这是Dijkstra算法的核心思想：贪心地选择当前最优解进行扩展。

优先队列的实现方式

// 定义状态元组：费用, x坐标, y坐标, 剩余油量
using State = tuple<int, int, int, int>;

// 小顶堆优先队列
priority_queue<State, vector<State>, greater<State>> pq;

这里使用了tuple来存储状态信息，并通过greater<State>指定小顶堆。tuple的比较是按字典序进行的，因此第一个元素（费用）决定了优先级。

为什么使用优先队列？

1. 保证最优性：总是先处理费用最小的状态，确保第一次到达终点时的解就是最优解
2. 提高效率：避免处理大量次优解，减少不必要的计算
3. 动态更新：当发现到达某个状态的更优路径时，可以将其重新加入队列

优先队列的操作

1. 插入元素：

   pq.push({cost, x, y, k});
   

2. 取出最小元素：

   auto [cur_cost, x, y, k] = pq.top();
   pq.pop();
   

3. 判断队列是否为空：

   while (!pq.empty()) {
       // 处理元素
   }
   

完整代码实现

#include <iostream>
#include <queue>
#include <tuple>
#include <cstring>
#include <climits>
using namespace std;

const int MAXN = 105;
const int MAXK = 15;
const int INF = 0x3f3f3f3f;

int N, K, A, B, C;
int oil[MAXN][MAXN];  // 油库分布
int dp[MAXN][MAXN][MAXK]; // dp[x][y][k]: 最小费用

int main() {
    // 读取输入
    cin >> N >> K >> A >> B >> C;
    for (int y = 1; y <= N; ++y) {
        for (int x = 1; x <= N; ++x) {
            cin >> oil[y][x];
        }
    }

    // 初始化DP数组
    memset(dp, 0x3f, sizeof(dp));
    dp[1][1][K] = 0;  // 起点状态

    // 优先队列：(费用, x, y, k)
    using State = tuple<int, int, int, int>;
    priority_queue<State, vector<State>, greater<State>> pq;
    pq.push({0, 1, 1, K});

    while (!pq.empty()) {
        auto [cur_cost, x, y, k] = pq.top();
        pq.pop();

        // 已存在更优解，跳过
        if (cur_cost > dp[x][y][k]) continue;

        // 到达终点，输出结果
        if (x == N && y == N) {
            cout << cur_cost << endl;
            return 0;
        }

        // 四个移动方向：右、下、左、上
        int dirs[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
        for (auto [dx, dy] : dirs) {
            int nx = x + dx, ny = y + dy;
            if (nx < 1 || nx > N || ny < 1 || ny > N) continue;

            // 计算移动费用
            int delta = (dx < 0 || dy < 0) ? B : 0;
            int newk = k - 1;
            if (newk < 0) continue;  // 油量不足

            int new_cost = cur_cost + delta;

            // 处理目标点
            if (oil[ny][nx]) {
                // 油库必须加油
                if (new_cost + A < dp[nx][ny][K]) {
                    dp[nx][ny][K] = new_cost + A;
                    pq.push({new_cost + A, nx, ny, K});
                }
            } else {
                // 不加油
                if (new_cost < dp[nx][ny][newk]) {
                    dp[nx][ny][newk] = new_cost;
                    pq.push({new_cost, nx, ny, newk});
                }
                // 增设油库
                if (new_cost + C + A < dp[nx][ny][K]) {
                    dp[nx][ny][K] = new_cost + C + A;
                    pq.push({new_cost + C + A, nx, ny, K});
                }
            }
        }
    }

    // 若未提前返回，遍历终点所有油量状态
    int res = INF;
    for (int k = 0; k <= K; ++k) {
        res = min(res, dp[N][N][k]);
    }
    cout << res << endl;

    return 0;
}

代码解析

1. 数据结构

• oil[MAXN][MAXN]：存储油库分布
• dp[MAXN][MAXN][MAXK]：动态规划表，记录每个状态的最小费用
• priority_queue：优先队列，按费用排序

2. 初始化

• 将dp数组初始化为INF（无穷大）
• 设置起点状态：dp[1][1][K] = 0

3. 主循环

1. 从队列取出当前最优状态
2. 检查是否到达终点
3. 尝试四个方向的移动：
   • 计算新位置和费用
   • 处理油库或增设油库的情况
   • 更新dp表并将新状态加入队列

4. 输出结果

找到终点(N,N)所有油量状态中的最小费用

算法流程详解

1. 初始化阶段

memset(dp, 0x3f, sizeof(dp)); // 初始化为极大值
dp[1][1][K] = 0;  // 起点状态：坐标(1,1)，满油K，费用0
pq.push({0, 1, 1, K}); // 初始状态入队

• 将整个dp表初始化为INF，表示初始时所有状态都不可达
• 设置起点状态：位于(1,1)，油量K，费用0
• 将起点状态加入优先队列

2. 主循环处理

while (!pq.empty()) {
    auto [cur_cost, x, y, k] = pq.top();
    pq.pop();
    
    if (cur_cost > dp[x][y][k]) continue;
    if (x == N && y == N) {
        cout << cur_cost << endl;
        return 0;
    }
    
    // 处理四个方向移动...
}

1. 取出当前费用最小的状态
2. 检查是否为更优解（防止重复处理）
3. 如果到达终点，直接输出结果（优先队列保证此时最优）

3. 状态转移处理

for (auto [dx, dy] : dirs) {
    int nx = x + dx, ny = y + dy;
    if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
    
    int delta = (dx < 0 || dy < 0) ? B : 0;
    int newk = k - 1;
    if (newk < 0) continue;
    
    int new_cost = cur_cost + delta;
    
    if (oil[ny][nx]) {
        // 油库处理逻辑...
    } else {
        // 非油库处理逻辑...
    }
}

• 遍历四个移动方向
• 计算新坐标(nx, ny)
• 确定移动费用delta（左/上移动支付B）
• 计算移动后剩余油量newk
• 计算新状态的总费用new_cost

(1) 遇到油库的情况

if (new_cost + A < dp[nx][ny][K]) {
    dp[nx][ny][K] = new_cost + A;
    pq.push({new_cost + A, nx, ny, K});
}

• 必须加油，支付费用A
• 油量重置为K
• 更新dp表并加入新状态到队列

(2) 非油库的情况

// 不加油
if (new_cost < dp[nx][ny][newk]) {
    dp[nx][ny][newk] = new_cost;
    pq.push({new_cost, nx, ny, newk});
}
// 增设油库
if (new_cost + C + A < dp[nx][ny][K]) {
    dp[nx][ny][K] = new_cost + C + A;
    pq.push({new_cost + C + A, nx, ny, K});
}

• 两种选择：

1. 不加油，继续行驶（油量减1）
2. 增设油库（支付C）并加油（支付A），油量重置为K

4. 输出结果

int res = INF;
for (int k = 0; k <= K; ++k) {
    res = min(res, dp[N][N][k]);
}
cout << res << endl;

• 遍历终点(N,N)所有可能的油量状态
• 取其中的最小费用作为最终结果

复杂度分析

• 时间复杂度：O(N²K log(N²K))
• 每个状态最多被处理一次
• 优先队列操作复杂度为log级别
• 空间复杂度：O(N²K)
• 存储dp表和优先队列

总结

这个解决方案结合了动态规划和Dijkstra算法的优点：

1. 动态规划记录子问题的最优解
2. 优先队列确保总是扩展最优状态
3. 正确处理了各种行驶和加油情况

对于N=100的网格，该算法也能高效运行。理解这个解决方案有助于掌握动态规划和图搜索算法的实际应用。通过优先队列的优化，我们有效地减少了需要处理的状态数量，提高了算法效率。

附：做题链接https://www.luogu.com.cn/problem/P4009