题目大意

场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。

Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。

设计一个程序，计算Jimmy到底地面时可能的最早时间。

DFS

这道题，爆搜显然是能找到正确答案的，我们从上往下跳，落到一个平台上的时候，只有两种选择，向左跑和向右跑，只要依次dfs这两种选择即可，但是数据量太大，会T。

#define inf 0x3f3f3f3f #define ll long long #define vec vector<int> #define P pair<int,int> #define MAX 1005 struct plat { int x1, x2, h; }ps[MAX]; bool cmp(plat p1, plat p2) { return p1.h > p2.h; } int T, N, X, Y, M, res; //当前遍历到第k个平台，他下坠的时候在x位置,y高度，一共用了t时间 void dfs(int k, int x, int y, int t) { if (k == N) {//坠落到地面 if (y <= M && t + y < res)res = t + y; return; } if (t + y > res || y - ps[k].h > M)//掉到这里一定摔死 return;//剪枝1：最少时间都超过结果值 if (x >= ps[k].x1&&x <= ps[k].x2) {//可以掉到这个平台上 dfs(k + 1, ps[k].x1, ps[k].h, t + x - ps[k].x1 + y - ps[k].h);//往左边走 dfs(k + 1, ps[k].x2, ps[k].h, t + ps[k].x2 - x + y - ps[k].h);//往右边走 } else dfs(k + 1, x, y, t); } int main() { scanf("%d", &T); while (T--) { scanf("%d %d %d %d", &N, &X, &Y, &M); for (int i = 0; i < N; i++) scanf("%d %d %d", &ps[i].x1, &ps[i].x2, &ps[i].h); sort(ps, ps + N, cmp); ps[N].x1 = -20000, ps[N].x2 = 20000, ps[N].h = 0;//最后一个平台是地面 res = inf; dfs(0, X, Y, 0); cout << res << endl; } }

DP

既然直接爆搜不可以，我们不妨思考一下如何进行简化，可以剪枝嘛？或者可以记忆化搜索嘛？对剪枝而言，上述程序已经用了一步，我暂时也没有想到很好的剪枝策略，而且数据范围这么大，应该很难剪到规定时限内吧。排除掉剪枝这个方法，唯一的优化策略就剩下了能不能将他转化为记忆化搜索/DP。

从顶向下飞，我们好像看不出来任何符合DP条件的东西，那么我们不妨从底向上分析。令

$dpl[k]$表示第k个平台从左侧下落到底部的最少用时$dpr[k]$表示第k个平台从右侧下落到底部的最少用时

为很么要分成这两部分呢？读者可以思考一下

假设我们有$n$个平台，高度从高到低排列，此时我们知道了后$k$个平台每个下降到底部的最少用时，那么如何确定第$k-1$的最小用时呢？

我们不妨遍历$j=k:n$中间的所有平台，如果从$k-1$的左侧下落能到达平台$j$，那么我们要进一步决定是从j的左侧下去，还是从j的右侧下去，从二者之中取一个最小的。这也就是为什么我需要两个dp数组。

在找到了所有平台左右两端下降到最低点的最小用时之后，我们就可以从起始点开始，找到他能够碰到的平台，取用时最少的操作即可。

不要忘了直接跳到地面的情况

//184K 0MS #define inf 0x3f3f3f3f #define ll long long #define vec vector<int> #define P pair<int,int> #define MAX 1005 struct plat { int x1, x2, h; }ps[MAX]; bool cmp(plat p1, plat p2) { return p1.h > p2.h; } int T, N, X, Y, M, dpl[MAX], dpr[MAX]; int main() { scanf("%d", &T); while (T--) { scanf("%d %d %d %d", &N, &X, &Y, &M); for (int i = 0; i < N; i++) scanf("%d %d %d", &ps[i].x1, &ps[i].x2, &ps[i].h); sort(ps, ps + N, cmp); ps[N].x1 = -200000, ps[N].x2 = 200000, ps[N].h = 0;//最后一个平台是地面 fill(dpl, dpl + MAX, inf); fill(dpr, dpr + MAX, inf); dpl[N] = 0; dpr[N] = 0; for (int i = N - 1; i >= 0; i--) { plat p = ps[i], t; bool ls = 1, rs = 1; for (int j = i + 1; j <= N && p.h - ps[j].h <= M && (ls || rs); j++) { t = ps[j]; //p可以从左边降落到t if (ls && p.x1 >= t.x1&&p.x1 <= t.x2) { //到这里后向左走下平台或者向右走下平台的最短的 int mi = min(p.x1 - t.x1 + dpl[j], t.x2 - p.x1 + dpr[j]); if (j == N)mi = t.h; if (mi + p.h - t.h < dpl[i]) dpl[i] = mi + p.h - t.h; ls = 0;//她从左边只能降落到离他最近的这个 } //p可以从右边降落到t if (rs && p.x2 >= t.x1&&p.x2 <= t.x2) { int mi = min(p.x2 - t.x1 + dpl[j], t.x2 - p.x2 + dpr[j]); if (j == N)mi = t.h; if (mi + p.h - t.h < dpr[i]) dpr[i] = mi + p.h - t.h; rs = 0; } } } int res = inf; for (int i = 0; i <= N && Y - ps[i].h <= M; i++) { plat p = ps[i]; if (X >= p.x1&&X <= p.x2) { int t = min(dpl[i] + X - p.x1, dpr[i] + p.x2 - X); if (i == N)t = 0;//需要考虑直接跳下来的情况 if (t + Y - p.h < res) res = t + Y - p.h; break; } } cout << res << endl; } }