题解

题面描述

在某异界大陆，从城池$A$到达城池$B$需要经过若干个传送阵。$A$城设有起点传送阵，$B$城设有终点传送阵。所有传送阵按一条直线排列，相邻传送阵之间的距离均为$1$。每个传送阵具有以下两个属性：

1. 最大传送距离$L$：每次使用该传送阵可以选择向前传送至最多$L$个传送阵之外的位置。
2. 能量消耗$i$：每次使用该传送阵进行传送需要消耗$i$个能量水晶。

传送阵只能向前传送，无法向后传送。修士小明从$A$城出发，携带一定数量的能量水晶，目标是到达$B$城。请问小明最少需要携带多少个能量水晶，才能顺利到达$B$城。

思路

本问题可以抽象为在一条线性排列的传送阵上寻找从起点到终点的最小能量消耗路径。由于每个传送阵只能向前传送，并且每次传送的距离和能量消耗各不相同，因此需要找到一种高效的策略来计算最小能量。

动态规划思路：

• 状态定义：

  • dp[i] 表示到达第 i 个传送阵所需的最小能量水晶。

• 状态转移方程：

  

• 初始化：

  • dp[0] = 0，表示从起点出发不消耗任何能量水晶。
  • 其他 dp[i] 初始化为无穷大，表示尚未到达。

• 最终答案：

  • dp[m] 即为到达终点所需的最小能量水晶。

优化方法：

由于传送阵的数量$m$可能高达$10^4$，直接使用动态规划可能会导致时间复杂度过高。为此，可以采用广度优先搜索（BFS）结合优先队列（最小堆），即Dijkstra算法，将问题转化为加权有向图的单源最短路径问题。

1. 构建图：

   • 每个传送阵视为图中的一个节点。
   • 从每个传送阵i，可以向i+1到i+L_i的传送阵建立有向边，边的权重为cost_i。

2. 应用Dijkstra算法：

   • 使用优先队列维护当前已知的最小能量消耗路径。
   • 从起点传送阵0开始，逐步扩展到可达的传送阵，更新各节点的最小能量消耗值。
   • 当终点$B$城（节点m）被访问时，当前的能量消耗即为最小值。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1e18;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int m;
    cin >> m;
    // 使用0-based索引，0到m-1为传送阵，m为终点
    vector<pair<int, int>> teleporters(m, {0, 0});
    for(int i=0;i<m;i++) cin >> teleporters[i].first >> teleporters[i].second;
    
    // dp[i]表示到达传送阵i的最小能量，0到m为终点
    vector<ll> dp(m+1, INF);
    dp[0] = 0;
    
    // 优先队列，存储{当前能量, 传送阵位置}
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, std::greater<pair<ll, int>>> pq;
    pq.push({0, 0});
    
    while(!pq.empty()){
        auto [cost, u] = pq.top(); pq.pop();
        if(u == m) break; // 到达终点
        if(cost > dp[u]) continue;
        
        int L = teleporters[u].first;
        int c = teleporters[u].second;
        // 传送到u+1到u+L，如果超过m则直接传送到终点
        for(int v = u+1; v <= min(u + L, m); v++){
            ll new_cost = cost + c;
            if(new_cost < dp[v]){
                dp[v] = new_cost;
                pq.push({new_cost, v});
            }
        }
    }
    
    cout << dp[m];
}

python

import sys
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    m = int(data[0])
    teleporters = []
    idx = 1
    for _ in range(m):
        L = int(data[idx])
        i = int(data[idx+1])
        teleporters.append((L, i))
        idx +=2
    # 终点无需传送能力，消耗
    # dp[i]表示到达第i个传送阵的最小能量，0到m为终点
    dp = [float('inf')] * (m+1)
    dp[0] = 0
    heap = []
    heapq.heappush(heap, (0, 0))
    while heap:
        cost, u = heapq.heappop(heap)
        if u == m:
            break
        if cost > dp[u]:
            continue
        L, c = teleporters[u]
        for v in range(u+1, min(u + L +1, m+1)):
            new_cost = cost + c
            if new_cost < dp[v]:
                dp[v] = new_cost
                heapq.heappush(heap, (new_cost, v))
    print(dp[m])

if __name__ == "__main__":
    main()

java

import java.util.*;
import java.io.*;

public class Main {
    static class Teleporter {
        int L;
        int cost;
        Teleporter(int L, int cost){
            this.L = L;
            this.cost = cost;
        }
    }
    
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        int m = Integer.parseInt(br.readLine());
        Teleporter[] teleporters = new Teleporter[m];
        for(int i=0;i<m;i++){
            String[] parts = br.readLine().trim().split("\\s+");
            int L = Integer.parseInt(parts[0]);
            int cost = Integer.parseInt(parts[1]);
            teleporters[i] = new Teleporter(L, cost);
        }
        // 终点无需传送能力，消耗
        
        long[] dp = new long[m+1];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0;
        
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b)->Long.compare(a[0], b[0]));
        pq.offer(new long[]{0, 0});
        
        while(!pq.isEmpty()){
            long[] current = pq.poll();
            long cost = current[0];
            int u = (int)current[1];
            if(u == m) break; // 到达终点
            if(cost > dp[u]) continue;
            Teleporter tp = teleporters[u];
            for(int v = u+1; v <= Math.min(u + tp.L, m); v++){
                long new_cost = cost + tp.cost;
                if(new_cost < dp[v]){
                    dp[v] = new_cost;
                    pq.offer(new long[]{new_cost, v});
                }
            }
        }
        System.out.println(dp[m]);
    }
}

题目内容

某异界大陆，从城池$A$到达城池$B$需要经历若干个传送阵，$A$城有起点传送阵，$B$城为终点，传送阵呈一字排开，相邻传送阵之间距离都为$1$。每个传送阵可传送距离是$1$到$L$，每次传送消耗的能量水晶$i$个，传送阵只能向前传送，不可向后。

修士小明携带若干能量水晶从$A$城出发，请问小明最少需要携带多少水晶才能到达$B$城。

输入描述

输入为多行:

第一行为整数$m(0<m<=10^4)$，表示接下来$m$行数组元素($m$个传送阵)

第二行至第$m+1$行为长度为2的整数数组，两个整数以空格隔开，第一个元素表示传送阵可传送的最大距离$L(0<L<=m)$，第二个元素表示该传送阵每次传送消耗的能量水晶个数$i(0<i<=10^4)$

输出描述

输出为整数，表示最少需要携带的水晶个数

样例1

输入

4
2 1
1 2
2 4
1 1

输出

5

说明

从下标$0$的传送阵出发，最优路径:

$0->2->B$城，,需要$5$个水晶。

到达B城最少需要$5$个水晶。

样例2

输入

4
1 1
2 2 
2 4
1 1

输出

4

说明

从下标$0$的传送阵出发，只能到达传送阵$1$，最优路径:

$0->1->3->B$城，,需要$4$个水晶。

到达B城最少需要$4$个水晶。