核心思想：离散化 + 线段树 + DP
离散化就不用说了（话说这题也没给数据范围），一套常规离散操作处理一下所有横坐标。
然后从低到高对每个板子在线段树上做区间赋值，并预处理出每个板子的左右落点。
最后像数字三角形一样做一下DP就好了。
DP的时候：
设dp[i][0/1]表示从左/右转移上来的最大值，判断纵向距离小于Max 就转移．
方程：
if (a[i].h - a[a[i].ld].h <= Max)
if (a[i].ld)
dp[i][0] = std::min(dp[a[i].ld][0] + cx[a[i].p] - cx[a[a[i].ld].p],
dp[a[i].ld][1] + cy[a[a[i].ld].p] - cx[a[i].p])
+ a[i].h - a[a[i].ld].h; else dp[i][0] = a[i].h;
if (a[i].h - a[a[i].rd].h <= Max)
if (a[i].rd)
dp[i][1] = std::min(dp[a[i].rd][0] + cy[a[i].p] - cx[a[a[i].rd].p],
dp[a[i].rd][1] + cy[a[a[i].rd].p] - cy[a[i].p])
+ a[i].h - a[a[i].rd].h; else dp[i][1] = a[i].h;
一些细节：
１.可以把铁球初始位置和地面看作板子。
２.转移的时候别忘了加上板子间的高度（我太傻了，调了三个小时就因为这个）．
AC代码:
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cctype> #include <cmath> inline void read(int & x) { int k = 1; x = 0; char c = getchar(); while (!isdigit(c)) if (c == '-') c = getchar(), k = -1; else c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); x *= k; } struct Node { int h, l, r, p, ld, rd; bool operator < (const Node & b) const { return h < b.h; }; } a[102020]; struct Tree { int l, r, w; }t[808080]; #define lson l, mid, u << 1 #define rson mid + 1, r, u << 1 | 1 #define root 1, N, 1 #define ls u << 1 #define rs u << 1 | 1 inline void push_down(int u) { t[ls].w = t[u].w, t[rs].w = t[u].w; t[u].w = 0; } void build(int l, int r, int u) { t[u].l = l, t[u].r = r; if (l == r) return; int mid = (l + r) >> 1; build(lson); build(rson); } void Add(int u, int l, int r, int c) { if (t[u].l >= l && t[u].r <= r) { t[u].w = c; return; } if (t[u].w) push_down(u); int mid = (t[u].l + t[u].r) >> 1; if (l <= mid) Add(ls, l, r, c); if (r > mid) Add(rs, l, r, c); } int Query(int l, int r, int u, int x) { if (l == r && l == x) return t[u].w; if (t[u].w) push_down(u); int mid = l + r >> 1; if (x <= mid) return Query(lson, x); if (x > mid) return Query(rson, x); } int n, Max, fx, fy, N, h[101010], cx[102020], cy[102020], lx[202020], dp[102020][2]; signed main() { memset(dp, 0x3f, sizeof(dp)); read(n), read(Max), read(fx), read(fy); for (int i = 1; i <= n; ++i) read(a[i].h), read(cx[i]), read(cy[i]), lx[++N] = cx[i], lx[++N] = cy[i], a[i].p = i; lx[++N] = fx, a[n + 1].h = fy; cx[n + 1] = cy[n + 1] = fx; a[0].h = 0, a[0].p = 0, a[n + 1].p = n + 1; std::sort(lx + 1, lx + N + 1); for (int i = 1; i <= n + 1; ++i) a[i].l = std::lower_bound(lx + 1, lx + N + 1, cx[i]) - lx, a[i].r = std::lower_bound(lx + 1, lx + N + 1, cy[i]) - lx; std::sort(a + 1, a + n + 2); build(1, N, 1); for (int i = 1; i <= n + 1; ++i) a[i].ld = Query(root, a[i].l), a[i].rd = Query(root, a[i].r), Add(1, a[i].l, a[i].r, i); for (int i = 1; i <= n + 1; ++i) { if (a[i].h - a[a[i].ld].h <= Max) if (a[i].ld) dp[i][0] = std::min(dp[a[i].ld][0] + cx[a[i].p] - cx[a[a[i].ld].p], dp[a[i].ld][1] + cy[a[a[i].ld].p] - cx[a[i].p]) + a[i].h - a[a[i].ld].h; else dp[i][0] = a[i].h; if (a[i].h - a[a[i].rd].h <= Max) if (a[i].rd) dp[i][1] = std::min(dp[a[i].rd][0] + cy[a[i].p] - cx[a[a[i].rd].p], dp[a[i].rd][1] + cy[a[a[i].rd].p] - cy[a[i].p]) + a[i].h - a[a[i].rd].h; else dp[i][1] = a[i].h; } printf("%d", dp[n + 1][1]); }