POJ1661 dp

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

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

设计一个程序，计算Jimmy到底地面时可能的最早时间。
这是一道DP问题，首先是要分析每一步的转态，首先我们很容易想到对于每一个平台，我们往左走可以到达平台和往右走可以到达的平台是确定的。我们就可以先预处理出这一部分。接着我们考虑到对于每平台，我们都有两种走法，左走和右走.然后走到下一个平台后，我们又是有左走和右走两个走法。如此反复直到最下面地面。
用f[i][0]表示到达i这个平台的左端点时的最少时间
用f[i][1]表示到达i这个平台的右端点时的最少时间
为什么是要表示到端点呢？因为到达板的位置不一样，往下走的时间也不一样，所以选择设计状态是到他们都会达到的端点时的状态。
然后我们从f[i][0]转移到j平台上我们就是从i平台的左端点走到下面的平台，但是走到下面的平台我们可以走到左端点，也可以走到右端点，这就分别都转移就可以了；
jump数组就是表示从i平台左端点往下走是哪个平台，从右端点是哪个平台。

f[jump[i][0]][0] = min(f[jump[i][0]][0], f[i][0] + (xian[i].h - xian[jump[i][0]].h) + (xian[i].x1 - xian[jump[i][0]].x1));
f[jump[i][0]][1] = min(f[jump[i][0]][1], f[i][0] + (xian[i].h - xian[jump[i][0]].h) + (xian[jump[i][0]].x2 - xian[i].x1));

只要实现了上面的转移方程所需要的jump数组，在循环转移一次，最后也就答案出来了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
#include<stack>
#define ll long long
using namespace std;
const long long max_ = 2e3 + 7;
inline int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
struct k {
	int x1, x2, h;
}xian[1000 + 50];
int n, x, y, MAX, xiann = 0;
bool cmp(const k &t1, const k &t2) {
	return t1.h > t2.h;
}
int jump[1000 + 50][2], f[1000 + 3][4];
int main() {
	int T; 
	while (scanf_s("%d", &T) != EOF) {
		while (T--) {
			int first, temptime = 0, xmax = -1;
			n = read(), x = read(), y = read(), MAX = read();
			x += 20000;
			for (int i = 1; i <= n; i++) {
				xian[i].x1 = (read() + 20000);
				xian[i].x2 = (read() + 20000);
				xmax = max(xmax, xian[i].x2);
				xian[i].h = read();
			}
			sort(xian + 1, xian + 1 + n, cmp);
			xian[n + 1].x1 = -20000;
			xian[n + 1].x2 = 1e9;
			xian[n + 1].h = 0;

			for (int i = 0; i <= n + 1; i++) {
				for (int j = 0; j <= 2; j++) {
					f[i][j] = 1e9;
				}
			}
			first = 0;
			for (int i = 1; i <= n; i++) {
				if (xian[i].x1 <= x && xian[i].x2 >= x) {
					first = i;
					temptime = y - xian[i].h;
					break;
				}
			}
			if (first == 0) {
				cout << y << endl;
				continue;
			}
			for (int i = 1; i <= n; i++) {
				for (int j = i + 1; j <= n + 1; j++) {
					if (jump[i][0] != 0 && jump[i][1] != 0) break;
					if (xian[j].h < xian[i].h && xian[j].x1 <= xian[i].x1 && xian[j].x2 >= xian[i].x1&&xian[i].h - xian[j].h <= MAX && jump[i][0] == 0) {
						//i这块板的左边第一个可以跳的
						jump[i][0] = j;
					}
					if (xian[j].h < xian[i].h && xian[j].x1 <= xian[i].x2 && xian[j].x2 >= xian[i].x2&&xian[i].h - xian[j].h <= MAX && jump[i][1] == 0) {
						//i这块板的右边第一个可以跳的
						jump[i][1] = j;
					}
				}
			}
			f[first][0] = (y - xian[first].h) + (x - xian[first].x1);
			f[first][1] = (y - xian[first].h) + (xian[first].x2 - x);
			int flag = 0;
			for (int i = first; i <= n; i++) {
				if (flag == 1 && xian[i].h == xian[first].h)continue;
				if (i == first) {
					flag = 1;
				}
				if (jump[i][0] != 0) {
					if (jump[i][0] == n + 1) {
						f[n + 1][0] = min(f[n + 1][0], f[i][0] + xian[i].h);
						f[n + 1][1] = min(f[n + 1][1], f[i][0] + xian[i].h);
					}
					else {
						f[jump[i][0]][0] = min(f[jump[i][0]][0], f[i][0] + (xian[i].h - xian[jump[i][0]].h) + (xian[i].x1 - xian[jump[i][0]].x1));
						f[jump[i][0]][1] = min(f[jump[i][0]][1], f[i][0] + (xian[i].h - xian[jump[i][0]].h) + (xian[jump[i][0]].x2 - xian[i].x1));
					}
				}
				if (jump[i][1] != 0) {
					if (jump[i][1] == n + 1) {
						f[n + 1][0] = min(f[n + 1][0], f[i][1] + xian[i].h);
						f[n + 1][1] = min(f[n + 1][1], f[i][1] + xian[i].h);
					}
					else {
						f[jump[i][1]][0] = min(f[jump[i][1]][0], f[i][1] + (xian[i].h - xian[jump[i][1]].h) + (xian[i].x2 - xian[jump[i][1]].x1));
						f[jump[i][1]][1] = min(f[jump[i][1]][1], f[i][1] + (xian[i].h - xian[jump[i][1]].h) + (xian[jump[i][1]].x2 - xian[i].x2));
					}
				}
			}
			cout << min(f[n + 1][1], f[n + 1][0]) << endl;
			for (int i = 0; i <= n; i++) {
				jump[i][1] = jump[i][0] = xian[i].h = xian[i].x1 = xian[i].x2 = 0;
			}
		}
	}
	return 0;
}