题解：坠落的最短路径（动态规划应用）

题目背景

本题为经典的平台坠落问题，要求计算物体从初始位置下落到地面（或最低平台）的最短路径。物体只能落在下方平台上，且每次下落高度不能超过给定的最大值。

问题描述

给定初始位置 $(x, y)$ 和 $n$ 个平台（每个平台由左端点 $x_1$、右端点 $x_2$ 和高度 $h$ 描述），所有平台按高度升序排列（地面视为高度为0的特殊平台）。物体从初始位置开始下落，每次只能落在下方平台上，且下落高度不超过 $maxs$。求物体到达地面的最短路径长度（路径由垂直下落高度和水平移动距离组成）。

算法思路：动态规划

采用动态规划（DP）解决，核心思想是状态转移：记录每个平台左右端点的最短路径，逐步推导到地面。

1. 状态定义：
   $dp[i][0]$：从第 $i$ 个平台的左端点下落到地面的最短路径长度。
   $dp[i][1]$：从第 $i$ 个平台的右端点下落到地面的最短路径长度。

2. 状态转移：
   对每个平台 $i$，找到其正下方第一个能接住的平台 $m$（即高度小于当前平台且覆盖当前平台端点的平台）。若存在平台 $m$ 且下落高度差不超过 $maxs$，则：

   • 从 $i$ 的左端点下落：路径长度为高度差（$h_i - h_m$）加上从 $m$ 的左/右端点到 $i$ 左端点的水平距离的最小值。
   • 从 $i$ 的右端点下落：同理，路径长度为高度差加上从 $m$ 的左/右端点到 $i$ 右端点的水平距离的最小值。

3. 边界条件：

   • 若下方无平台且当前高度 $h_i \leq maxs$，则路径长度为 $h_i$（直接下落到地面）。
   • 若下方无平台但 $h_i > maxs$，则无法到达（路径长度设为无穷大）。

代码解释

以下是关键代码的详细说明：

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

const int inf = 0x3f3f3f3f; // 表示无穷大

// 平台结构体：左端点l、右端点r、高度h
struct Point {
    int l;
    int r;
    int h;
    Point(int _l, int _r, int _h) : l(_l), r(_r), h(_h) {};
    // 按高度升序排序
    bool operator < (const Point &p) const {
        return h < p.h;
    }
};

vector<Point> p_v; // 存储所有平台（包括初始点）
int dp[1010][2];   // dp[i][0]：第i个平台左端点的最短路径；dp[i][1]：右端点

// 查找当前平台下方第一个能接住的平台（index为当前平台索引，p为当前端点坐标）
int find_black(int index, int p) {
    // 从下往上遍历（已排序，下方平台索引更小）
    for (int i = index - 1; i >= 0; i--) {
        if (p_v[i].l <= p && p_v[i].r >= p) {
            return i; // 返回下方平台的索引
        }
    }
    return inf; // 无平台接住
}

// 计算最短路径的核心函数（n为平台数，maxs为最大允许下落高度）
int drop(int n, int maxs) {
    // 初始化：初始点（第0个平台）的左右端点路径为初始高度
    dp[0][1] = dp[0][0] = p_v[0].h;
    
    for (int i = 1; i <= n; ++i) { // 遍历每个平台（i=0是初始点）
        int m; // 下方接住的平台索引
        
        // 处理当前平台左端点
        m = find_black(i, p_v[i].l);
        if (m != inf) { // 下方有平台
            if (p_v[i].h - p_v[m].h <= maxs) {
                // 路径 = 高度差 + min（从m左端点走到当前左端点，从m右端点走到当前左端点）
                dp[i][0] = (p_v[i].h - p_v[m].h) + 
                           min(dp[m][0] + (p_v[i].l - p_v[m].l), 
                               dp[m][1] + (p_v[m].r - p_v[i].l));
            } else {
                dp[i][0] = inf; // 下落高度超过maxs，不可达
            }
        } else { // 下方无平台
            if (p_v[i].h <= maxs) {
                dp[i][0] = p_v[i].h; // 直接下落到地面
            } else {
                dp[i][0] = inf; // 高度过高，不可达
            }
        }
        
        // 处理当前平台右端点（逻辑同左端点）
        m = find_black(i, p_v[i].r);
        if (m != inf) {
            if (p_v[i].h - p_v[m].h <= maxs) {
                dp[i][1] = (p_v[i].h - p_v[m].h) + 
                           min(dp[m][0] + (p_v[i].r - p_v[m].l), 
                               dp[m][1] + (p_v[m].r - p_v[i].r));
            } else {
                dp[i][1] = inf;
            }
        } else {
            if (p_v[i].h <= maxs) {
                dp[i][1] = p_v[i].h;
            } else {
                dp[i][1] = inf;
            }
        }
    }
    // 初始点（第0个平台）的左右端点的最短路径最小值
    return min(dp[n][0], dp[n][1]);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, x, y, maxs;
        cin >> n >> x >> y >> maxs;
        memset(dp, 0, sizeof(dp)); // 初始化dp数组
        p_v.clear(); 
        
        // 初始位置作为一个特殊平台（左右端点均为x，高度为y）
        p_v.push_back(Point(x, x, y));
        for (int i = 0; i < n; ++i) {
            int x1, x2, h;
            cin >> x1 >> x2 >> h;
            p_v.push_back(Point(x1, x2, h));
        }
        sort(p_v.begin(), p_v.end()); // 按高度升序排序（包括初始点）
        
        cout << drop(n, maxs) << endl;
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n$ 为平台数。每个平台需要遍历其下方所有平台，最坏情况下为 $O(n^2)$。
• 空间复杂度：$O(n)$，用于存储平台信息和DP数组。