题目：
“Help Jimmy” 是在下图所示的场景上完成的游戏。
场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。
Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。
设计一个程序，计算Jimmy到底地面时可能的最早时间。 Input 第一行是测试数据的组数t（0 <= t <= 20）。每组测试数据的第一行是四个整数N，X，Y，MAX，用空格分隔。N是平台的数目（不包括地面），X和Y是Jimmy开始下落的位置的横竖坐标，MAX是一次下落的最大高度。接下来的N行每行描述一个平台，包括三个整数，X1[i]，X2[i]和H[i]。H[i]表示平台的高度，X1[i]和X2[i]表示平台左右端点的横坐标。1 <= N <= 1000，-20000 <= X, X1[i], X2[i] <= 20000，0 < H[i] < Y <= 20000（i = 1..N）。所有坐标的单位都是米。
Jimmy的大小和平台的厚度均忽略不计。如果Jimmy恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保证问题一定有解。 Output 对输入的每组测试数据，输出一个整数，Jimmy到底地面时可能的最早时间。 Sample Input 1 3 8 17 20 0 10 8 0 10 13 4 14 3 Sample Output 23
思路： 这题真的是一言难尽，卡了很久，最后发现状态转移那里手误了。。 网上搜到的题解大多和我的枚举方向不一样，我还以为是这个问题，结果后来仔细看了一遍，像我这样从高往低处也是可以的。 我用的dp[i][2]表示从上往下落到第i块平台的最短时间，dp[i][0]表示从上往下落到第i块平台+在第i块平台向左跑的时间，dp[i][1]表示从上往下落到第i块平台+在第i块平台向右跑的时间。 将下落点看作一个平台，将地面看作最后一个平台，所以最后就是求dp[n+2][2]的值。 每次要更新三个值，dp[i][0~2]。要判断能否从j直接落到i块。 这里的排序也是必要的。
代码：
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; #define LL long long const int maxn = 1050; const int inf = 0x3f3f3f3f; int dp[maxn][3]; struct node { int x,y,h; }data[maxn]; bool cmp(node a,node b) { return a.h > b.h; } int check(int a,int b) //检查a的两个端点是否被覆盖 { int visx = 1,visy = 1; for(int i = a+1 ; i < b ; i++) { if(data[i].x <= data[a].x && data[i].y >= data[a].x) visx = 0; if(data[i].x <= data[a].y && data[i].y >= data[a].y) visy = 0; } if(visx+visy == 0) return 0; else if(visx+visy == 2) return 3; else if(visx == 1) return 1; else if(visy == 1) return 2; } int main() { int t; scanf("%d",&t); while(t--) { int n,X,Y,maxh; for(int i = 0; i < maxn; i++) for(int j = 0; j < 3; j++) dp[i][j] = inf; scanf("%d%d%d%d",&n,&X,&Y,&maxh); for(int i = 2; i <= n+1 ; i++) scanf("%d%d%d",&data[i].x,&data[i].y,&data[i].h); data[1].x = X,data[1].y = X,data[1].h = Y; data[0].x = X,data[0].y = X; sort(data+2,data+n+2,cmp); dp[1][0] = dp[1][1] = 0; data[n+2].x = -20005,data[n+2].y = 20005,data[n+2].h = 0; for(int i = 2; i <= n+2 ; i++) { int res = inf; for(int j = i-1; j >= 1; j--) { if(data[j].h - data[i].h > maxh) continue; int op = check(j,i); if(op == 0) continue; if(data[j].x <= data[i].y && data[j].x >= data[i].x && (op == 1 || op == 3)) { res = min(res,dp[j][0] + data[j].h - data[i].h); dp[i][2] = res; dp[i][0] = min(dp[j][0] + data[j].h - data[i].h+abs(data[i].x - data[j].x),dp[i][0]);//就是这里写错了，直接res+向左的距离。也是智障的不行 dp[i][1] = min(dp[j][0] + data[j].h - data[i].h+abs(data[i].y - data[j].x),dp[i][1]); } if(data[j].y >= data[i].x && data[j].y <= data[i].y &&(op == 2 || op == 3)) { res = min(res,dp[j][1] + data[j].h - data[i].h); dp[i][2] = res; dp[i][0] = min(dp[j][1] +data[j].h - data[i].h+ abs(data[i].x-data[j].y),dp[i][0]); dp[i][1] = min(dp[j][1] +data[j].h - data[i].h+ abs(data[i].y-data[j].y),dp[i][1]); } } } printf("%d\n",dp[n+2][2]); } return 0; }